两数之和

## 题目

> 题目来源：[1. 两数之和](https://leetcode-cn.com/problems/two-sum)。

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

**示例 1：**

```txt
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
```

**示例 2：**

```txt
输入：nums = [3,2,4], target = 6
输出：[1,2]
```

**示例 3：**

```txt
输入：nums = [3,3], target = 6
输出：[0,1]
```

**提示：**

* 2 <= nums.length <= 103
* -109 <= nums[i] <= 109
* -109 <= target <= 109
* 只会存在一个有效答案

## 问题解析

1. HashMap 的基本思想是**当判断一个数组中是否存在两个数的和为目标值时，可以通过判断数组中是否存在和目标元素-当前元素的值**。
2. 因此我们可以通过**Hash 映射**的方法，其中 $key$ 为元素值，$value$ 为其对应的数组下表，从而减少查找的次数。

## 参考代码

```java
/**
 * 1. 两数之和
 * @param nums  数组
 * @param target    目标值
 * @return  和为目标值的两个整数的下标
 */
public int[] twoSum(int[] nums, int target) {
    HashMap<Integer, Integer> map = new HashMap<>();
    
    for (int i = 0; i < nums.length; i++) {
        if (map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i) {return new int[]{i, map.get(target - nums[i])};}
        map.put(nums[i], i);
    }
    
    return new int[]{};
}
```

## 扩展题目

### 元素未排序，包含重复元素，输出所有数对

#### 问题解析

1. 由于包含重复元素，所以我们需要对上面使用的哈希表进行修改：
   1. **$key$依然是数组中的元素**，$value$**改为对应元素在数组中的索引队列**。
2. 初始时将所有元素及其对应于数组中的索引队列存入哈希表中。
3. 在遍历数组中的元素时，假设当前元素为 $key$，$temp$ 为目标和 $target$ 与 $key$ 的差，即 $temp = target - key$，当满足以下情况时更新结果数组：
   1. **哈希表中包含**$temp$。
   2. $temp$**的索引队列不为空**。
   3. $key$**和**$temp$**的索引队列队顶元素不相等**（为了处理数组为[3]，目标和为 6 的情况）。
4. 注意事项：
   1. **结果数组赋值时元素对应的下标需要从索引队列中取**，**这样主要为了避免元素重复判断**：`res[index++] = new int[]{map.get(key).poll(), map.get(temp).poll()};`
   2. **如果当前元素已用完**，**则将其从哈希表中移除**：`if (map.get(temp).size() == 0) {map.remove(key);}`。

#### 参考代码

```java
/**
 * 1. 两数之和（包含重复元素，输出所有数对）
 * @param numbers   数组
 * @param target    目标和
 */
public static int[][] twoSum (int[] numbers, int target) {
    Map<Integer, Queue<Integer>> map = new HashMap<>(); //  key 为元素，value 为元素在数组中的索引队列
    int[][] res = new int[numbers.length / 2][];
    int index = 0;

/**
     * 存储数组元素及其对应于数组中的索引队列
     */
    for (int i = 0; i < numbers.length; i++) {
        int key = numbers[i];
        Queue<Integer> queue = new LinkedList<>();
        if (!map.containsKey(key)) {queue = new LinkedList<>();} 
        else {queue = map.get(key);}
        queue.offer(i + 1);
        map.put(key, queue);
    }

/**
     * 获取目标和为 target 的全部数对
     */
    for (int i = 0; i < numbers.length; i++) {
        int key = numbers[i];
        int temp = target - key;
        if (map.containsKey(temp) && map.get(temp).size() > 0 && map.get(key).peek() != map.get(temp).peek()) {
            //  map.get(key).peek() != map.get(temp).peek() 是为了处理 [3] target = 6 的特殊情况
            res[index++] = new int[]{map.get(key).poll(), map.get(temp).poll()};
            if (map.get(temp).size() == 0) {map.remove(key);}   //  如果当前元素已用完，则将其从 map 中移除
        }
    }
    return res;
}
```

### 元素已排序，常量级额外空间

#### 问题解析

1. 因为元素已排序，所以可以考虑使用**二分法**查找目标和减去当前元素对应的元素。

#### 参考代码

```java
/**
 * 1. 两数之和（元素已排序，常量级额外空间）
 * @param numbers   数组
 * @param target    目标和
 */
public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length; i++) {
        int temp = search(numbers, target - numbers[i], i + 1, numbers.length - 1);
        if (temp != -1) {return new int[]{i + 1, temp + 1};}
    }
    return new int[2];
}

/**
 * 二分查找
 * @param numbers   数组
 * @param num   目标元素
 * @param _left 左边界
 * @param _right    右边界
 */
public int search(int[] numbers, int num, int _left, int _right) {
    int left = _left, right = _right;
    while (left <= right) {
        int mid = mid = left + (right - left) / 2;
        if (numbers[mid] < num) {left = mid + 1;}
        else if (numbers[mid] > num) {right = mid - 1;}
        else if (numbers[mid] == num) {return mid;}
    }
    return -1;
}
```

## 相关题目

### 三数之和

> 题目来源：[15. 三数之和](https://leetcode-cn.com/problems/3sum)。

#### 题目

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

**注意：** 答案中不可以包含重复的三元组。

**示例 1：**

```txt
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
```

**示例 2：**

```txt
输入：nums = []
输出：[]
```

**示例 3：**

```txt
输入：nums = [0]
输出：[]
```

**提示：**

* 0 <= nums.length <= 3000
* -105 <= nums[i] <= 105

#### 问题解析

1. 先对原来的数组进行排序。
2. 假设数组 $nums$ 的长度为 $len$。
3. 首先固定一个点 $nums[i]$，进行 **第一次去重** :information_desk_person: ，如果 $nums[i]==nums[i+1]$，则进行下一个循环。
4. 然后分别定义左、右指针：

$$
left = i + 1
$$

$$
right = len - 1
$$

5. 定义 $sum$：

$$
sum = nums[i] + nums[left] + nums[right]
$$

6. 对 $sum$ 进行判断：

* 如果 $sum>0$，$left++$。
   * 如果 $sum < 0$，$right--$。
   * 如果 $sum = 0$，将 $[nums[i],nums[left],nums[right]]$ 添加到结果中，同时 $left++,right--$，然后进行 **第二次去重** :information_desk_person: ：

$$
   while(left < right \space and \space nums[left] == nums[left+1]) \space left++
   $$

$$
   while(left < right \space and \space nums[right] == nums[right-1]) \space right—
   $$

![](https://notebook.ricear.com/media/202105/15-三数之和（双指针法）_1621948196.gif)

#### 参考代码

~~~java
/**
 * 15. 三数之和
 * @param nums  数组
 * @return  和为 0 且不重复的三元组
 */
public List<List<Integer>> threeSum(int[] nums) {
  int len = nums.length, left, right, sum;
  List<List<Integer>> res = new ArrayList<>();
  
  if (len < 3) {return res;}	//  如果数组的长度大于 3，说明不符合题意，直接返回空数组即可
  
  Arrays.sort(nums);
  for (int i = 0; i < len; i++) {
    if (nums[i] > 0) {continue;}	//  如果第一个元素都大于 0， 说明后面的元素肯定大于 0，则三者之和肯定大于 0，继续进行下一个循环即可
    /** 第一次去重 **/
    if (i > 0 && nums[i] == nums[i - 1]) {continue;}	//  如果第一个元素前后两个一样，则最后的结果可能和前面的结果重复
    
    left = i + 1;right = len - 1;
    while (left < right) {
      sum = nums[i] + nums[left] + nums[right];
      if (sum < 0) {left++;}
      else if (sum > 0) {right--;}
      else if (sum == 0) {
        res.add(Arrays.asList(nums[i], nums[left], nums[right]));
        /** 第二次去重 **/
        while (left < right && nums[left] == nums[left+1]) {left++;}	//  如果左指针对应元素和其下一个元素相同，则最后的结果可能和前面的结果重复，直接将左指针向后面移动一位即可
        while (left < right && nums[right] == nums[right-1]) {right--;}	//  如果右指针对应元素和其上一个元素相同，则最后的结果可能和前面的结果重复，直接将右指针向前面移动一位即可
        left++;right--;	//  将左指针右移，右指针左移
      }
    }
  }
  return res;
}
~~~

## 参考文献

1. [画解算法：15. 三数之和](https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn)。