一、題目

難度：簡單

給定一個整數(shù)數(shù)組? nums 和一個整數(shù)目標(biāo)值? target，請你在該數(shù)組中找出 和為目標(biāo)值 target  的那 兩個 整數(shù)，并返回它們的數(shù)組下標(biāo)。你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素在答案里不能重復(fù)出現(xiàn)。你可以按任意順序返回答案。?

二、示例

示例 1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

?

示例 2：

輸入：nums = [3,2,4], target = 6
輸出：[1,2]

?

示例 3：

輸入：nums = [3,3], target = 6
輸出：[0,1]

?

三、簡單分析

?簡單理解一下哈，力扣直接標(biāo)記出簡單，說實話，對于一個算法不太了解的人，確實不太明白。通過一些資料慢慢理解了。在這里分享給大家，主要是思路。

給我們一個數(shù)組，然后一個目標(biāo)值。我們不用想要得到數(shù)組下標(biāo)，肯定要進行便利數(shù)組，然后進行比較找出答案。最簡單的就是兩個便利然后組合進行判斷是否符合目標(biāo)值?，當(dāng)然這樣的效率也是比較慢，隨著數(shù)組的越大，效率就會直線下降。這樣的時間復(fù)雜度為O(n^2)。就和冒泡排序一樣兩個for進行挨個比較！?

?

四、暴力便利

public static int[] twoSum1(int[] nums,int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return null;
}
public static void main(String[] args) {
    int nums[] = {2,4,6,7};
    int target = 10;
    int[] ints = twoSum1(nums, target);
    for (int i = 0;i < ints.length; i++){
        System.out.println(ints[i]);
    }
}

五、進階HashMap實現(xiàn)

public int[] twoSum2(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int result = target - nums[i];
        if (map.containsKey(result)) {
            return new int[] { map.get(result), i };
        }
        map.put(nums[i], i);
    }
    return new int[]{};
}

public static void main(String[] args) {
    int nums[] = {2,4,6,7};
    int target = 6;
    int[] ints = twoSum2(nums, target);
    for (int i = 0;i < ints.length; i++){
        System.out.println(ints[i]);
    }
}

六、進階分析

利用HashMap的containsKey()?方法，哈希查找效率提升到O(n)?，遍歷數(shù)組 nums，i為當(dāng)前下標(biāo)，每個值都判斷map中是否存在 target-nums[i]?的key值，每次都把沒找到的放進集合里，以例子來說：第一次便利2   ?6 - 2 = 4? ，判斷map里沒有4這個key?，我們把i的值2放進map里key為值，value為下標(biāo)。第二次便利4   ?6 - 4 = 2?，判斷map，發(fā)現(xiàn)key有2?，則直接返回結(jié)果作為key的map對應(yīng)的value也就是0?下標(biāo)，第二個就是本次便利的i=4的下標(biāo)1依次放下進行繼續(xù)遍歷找到為止。