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