兩數(shù)之和 的題目是:

給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那兩個(gè)整數(shù)，并返回他們的數(shù)組下標(biāo)。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。

示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

首先想到的就是暴力的解法，兩層循環(huán)遍歷數(shù)組兩次，找到和為目標(biāo)值target的兩個(gè)數(shù)，返回下標(biāo)。代碼如下：

public int[] twoSum(int[] nums, int target) {
    for(int i = 0; i < nums.length; i++){
        for(int j = i + 1; j < nums.length; j++){
            if(nums[j] == target - nums[i]){
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");  
}

在 leetcode 提交代碼后運(yùn)行時(shí)間 35ms 左右，因?yàn)橛玫氖潜哭k法，遍歷兩次數(shù)組的時(shí)間復(fù)雜度是O(n^2)，耗時(shí)會(huì)隨著數(shù)組大小的增大而指數(shù)增加。

后來(lái)發(fā)現(xiàn)用 map 存儲(chǔ)一下數(shù)據(jù)的話，可以做到 O(n) 的時(shí)間復(fù)雜度。思路就是把數(shù)組的每個(gè) item 的值作為 key，對(duì)應(yīng)的下標(biāo)作為 value 存入 map，這樣每次存之前都先算出當(dāng)前數(shù)組 item 的值和 target 的差值作為待查的 key， 讓 map 查找這個(gè) key 是否存在，存在即找到正確的結(jié)果，取出對(duì)應(yīng) key 的 value 和當(dāng)前遍歷的 index 返回就行。

因?yàn)槔?HashMap 查找 key 理想情況下為 O(1) 的時(shí)間復(fù)雜度的特性，只用遍歷一遍數(shù)組就能完成任務(wù)，所以時(shí)間復(fù)雜度是 O(n)。代碼如下：

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    
    for(int i = 0; i < nums.length; i++){
        int sub = target - nums[i];
        if(map.containsKey(sub)){
            return new int[]{map.get(sub), i};
        }
        map.put(nums[i], i);
    }
    
    throw new IllegalArgumentException("No two sum solution");
}

提交后耗時(shí)6ms。

思路重點(diǎn)：

關(guān)鍵就在于對(duì)于 map 的運(yùn)用，對(duì)于 hash 函數(shù)的理解，想要最快速確定集合中元素是否存在，要能有意識(shí)的想到 map。