两个数的和（给定一个整数数组，当数组内两个数的和等于一个特定的值时返回两个数的下标）

客官°小女子只卖身不卖艺 2022-05-27 05:23 186阅读 0赞

例如，给定数组 num=\[2,7,11,15\],target=9,

因为num\[0\]+num\[1\]=2+7=9,

所以返回\[0,1\].

方法一蛮力法/暴力法：

蛮子法比较简单，遍历数组的每个元素x并且发现是否存在另一个元素的值=target-x.

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");
    }

复杂度分析：时间复杂度O(n2)，对于每个元素，我们试图通过遍历剩余的数组来发现元素这话费了O(n)O(n)时间，因此时间，因此时间复杂度为O（n2).空间复杂度为O(1).

方法二双循环哈希表法

为了改善运行时间复杂度，我们需要一种更有效的方式去检测是否补集存在这个数组中，如果补集存在，我们就查找它的下标，保持数组中的每个元素到其下标的映射的最好的方式是什么呢？？哈希表！！！

我们减少了查找时间从O（n）到O（1）以空间换速度。哈希表就是为了这个目的建立的。

我们用两次迭代进行一个简单的实现，第一次，我们把每个元素的值和下标(索引）添加到哈希表中，第二次，我们检查是否每个元素的补集存在哈希表中，注意：这个补集一定不能是num\[i\]本身。

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

时间复杂度O（n）空间复杂度O（n）

方法三单循环哈希表:

我们也可以用一次循环来做，当我们迭代将元素插入哈希表的时候，我们也可以查找是否当前元素的补集存在于哈希表中，，如果存在，立即返回。

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

时间复杂度O(n),我们只遍历了一次包含N个元素的列表，每次查找哈希表只需要O（1）时间

空间复杂度O(n).