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

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

例如，给定数组 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");
}