今天去某在線教育面試面試官讓做的一道題，題目描述如下：
很多人一想可能就是兩層for循環(huán)，我想了很久最后寫了雙重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ì)VeVb武林網(wǎng)的支持。
新聞熱點(diǎn)
疑難解答
圖片精選
