Java查找不重復無序數(shù)組中是否存在兩個數(shù)字的和為某個值
更新時間：2019年01月03日 14:20:52 作者：sdr_zd
今天小編就為大家分享一篇關(guān)于Java查找不重復無序數(shù)組中是否存在兩個數(shù)字的和為某個值，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧
今天去某在線教育面試面試官讓做的一道題，題目描述如下：
- 給定一個不重復的無序數(shù)組arr和一個定值num
- 查找arr中是否有兩個數(shù)的和等于num
- 有則返回這兩個數(shù)的下標(可能有多組, 只用返回一組), 沒有則返回null
很多人一想可能就是兩層for循環(huán)，我想了很久最后寫了雙重for循環(huán)…【這個代碼太easy就不放了】然后面試官說知道哈希嗎，由于哈希查找的時間復雜度是O(1)，從哈希的角度去考慮，這中間還有一堆就不描述了，說一下怎么用哈希實現(xiàn)。
實現(xiàn)思路：
將數(shù)組中的所有的值放入HashMap的Key中，Value存放該值對應的下標，遍歷這個HashMap，取得Key，計算如果可以和這個Key加起來的和為num的值，如果這個值存在，就直接返回這兩個下標。遍歷一次的時間復雜度為O(N)，查找的時間復雜度是O(1)，總體時間復雜度O(N)。
代碼實現(xiàn)：
public class getTwoNumsSumEquals {
public static void main(String[] args) {
int[] arr = new int[]{3, 4, 6, 5, 9, 8};
int num = 8;
int[] ret = getIndex(arr, num);
System.out.println("index of two numbers R:" + ret[0] + " " + ret[1]);
}
// 找到這兩個數(shù)的下標并返回（以長度為2的數(shù)組的形式返回）
private static int[] getIndex(int[] arr, int num) {
int[] ret = new int[2];
HashMap<Integer, Integer> hashMap = new HashMap<>();
int index = 0;
// 將每個數(shù)字和其下標放進map中
for (Integer curr : arr) {
hashMap.put(curr, index++);
}
// 遍歷HashMap并判斷
for (Map.Entry<Integer, Integer> entry : hashMap.entrySet()) {
int value = entry.getKey();
int subValue = num - value;
if(hashMap.containsKey(subValue)) {
// 找到啦!
ret[0] = entry.getValue();
ret[1] = hashMap.get(subValue);
break;
}
}
return ret;
}
}
總結(jié)
以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值，謝謝大家對腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接
相關(guān)文章
這篇文章主要介紹了Java中redis的基本類型，redis存儲數(shù)據(jù)的基本類型有：字符串類型、散列類型、列表類型、集合類型、有序集合類型，下面我們對其中幾個進行簡單介紹，需要的小伙伴可以參考一下2022-03-03
下面小編就為大家分享一篇java的JsonObject對象提取值方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-03-03
這篇文章主要為大家詳細介紹了Java如何通過操作FTP實現(xiàn)上傳下載的功能，文中的示例代碼講解詳細，對我們學習Java有一定幫助，需要的可以參考一下2022-11-11
使用Java代碼獲取服務器性能信息及局域網(wǎng)內(nèi)主機名
這篇文章主要介紹了使用Java代碼獲取服務器性能信息及局域網(wǎng)內(nèi)主機名的方法,方便對服務器的遠程管理和團隊協(xié)作時用到,而且文中的方法無需調(diào)用jni,需要的朋友可以參考下2015-11-11
這篇文章主要為大家詳細介紹了Java實現(xiàn)圖像分割功能，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
Springboot結(jié)合Flowable實現(xiàn)工作流開發(fā)
本文主要介紹了Springboot結(jié)合Flowable實現(xiàn)工作流開發(fā)，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
解析SpringBoot @EnableAutoConfiguration的使用
這篇文章主要介紹了解析SpringBoot @EnableAutoConfiguration的使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-09-09
這篇文章主要為大家詳細介紹了將視頻按照時間維度進行剪切的Java工具類，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起了解一下2022-12-12
spring boot2.0圖片上傳至本地或服務器并配置虛擬路徑的方法
最近寫了關(guān)于圖片上傳至本地文件夾或服務器，上傳路徑到數(shù)據(jù)庫，并在上傳時預覽圖片。本文通過實例代碼給大家分享spring boot2.0圖片上傳至本地或服務器并配置虛擬路徑的方法，需要的朋友參考下2018-12-12
這篇文章主要為大家介紹了IDEA版Postman的強大功能介紹，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-06-06