Java查找不重復(fù)無(wú)序數(shù)組中是否存在兩個(gè)數(shù)字的和為某個(gè)值
今天去某在線教育面試面試官讓做的一道題，題目描述如下：
- 給定一個(gè)不重復(fù)的無(wú)序數(shù)組arr和一個(gè)定值num
- 查找arr中是否有兩個(gè)數(shù)的和等于num
- 有則返回這兩個(gè)數(shù)的下標(biāo)(可能有多組, 只用返回一組), 沒(méi)有則返回null
很多人一想可能就是兩層for循環(huán)，我想了很久最后寫(xiě)了雙重for循環(huán)…【這個(gè)代碼太easy就不放了】然后面試官說(shuō)知道哈希嗎，由于哈希查找的時(shí)間復(fù)雜度是O(1)，從哈希的角度去考慮，這中間還有一堆就不描述了，說(shuō)一下怎么用哈希實(shí)現(xiàn)。
實(shí)現(xiàn)思路：
將數(shù)組中的所有的值放入HashMap的Key中，Value存放該值對(duì)應(yīng)的下標(biāo)，遍歷這個(gè)HashMap，取得Key，計(jì)算如果可以和這個(gè)Key加起來(lái)的和為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線程讓步y(tǒng)ield用法實(shí)例分析
這篇文章主要介紹了Java線程讓步y(tǒng)ield用法,結(jié)合實(shí)例形式分析了java中yield()方法的功能、原理及線程讓步操作的相關(guān)實(shí)現(xiàn)技巧,需要的朋友可以參考下2019-09-09
這篇文章主要為大家詳細(xì)介紹了Java基于Tcp/ip連接的多人交互聊天室，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-07-07
springboot登錄攔截器+ThreadLocal實(shí)現(xiàn)用戶信息存儲(chǔ)的實(shí)例代碼
ThreadLocal 為變量在每個(gè)線程中創(chuàng)建了一個(gè)副本,這樣每個(gè)線程都可以訪問(wèn)自己內(nèi)部的副本變量,這篇文章主要介紹了springboot登錄攔截器+ThreadLocal實(shí)現(xiàn)用戶信息存儲(chǔ)的實(shí)例代碼,需要的朋友可以參考下2024-03-03
使用Spring Boot Mybatis 搞反向工程的步驟
這篇文章主要介紹了使用Spring Boot Mybatis 搞反向工程的步驟，幫助大家更好的理解和使用spring boot框架，感興趣的朋友可以了解下2021-01-01
這篇文章主要為大家詳細(xì)介紹了Java的布隆過(guò)濾器，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-03-03
Java如何獲取當(dāng)前進(jìn)程ID以及所有Java進(jìn)程的進(jìn)程ID
本篇文章主要介紹了Java如何獲取當(dāng)前進(jìn)程ID以及所有Java進(jìn)程的進(jìn)程ID，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-06-06
Java 高并發(fā)九：鎖的優(yōu)化和注意事項(xiàng)詳解
本文主要介紹Java高并發(fā)鎖的優(yōu)化和注意事項(xiàng)，這里整理了詳細(xì)的資料，并講解了 1. 鎖優(yōu)化的思路和方法 2. 虛擬機(jī)內(nèi)的鎖優(yōu)化 3. 一個(gè)錯(cuò)誤使用鎖的案例 4. ThreadLocal及其源碼分析等知識(shí)，有需要的小伙伴可以參考下2016-09-09
Java中ThreadLocal使用原理及Synchronized區(qū)別
ThreadLocal叫做線程變量，本文詳細(xì)的介紹了ThreadLocal使用原理及Synchronized區(qū)別，有需要的朋友可以參考一下，希望對(duì)你有所幫助。2023-05-05
這篇文章主要給大家介紹了關(guān)于mybatis插入與批量插入返回ID的原理的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用mybatis具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07
解決RestTemplate加@Autowired注入不了的問(wèn)題
這篇文章主要介紹了解決RestTemplate加@Autowired注入不了的問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。2021-08-08