三数之和

两数之和

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9，因为 nums[0] + nums[1] = 2 + 7 = 9，所以返回 [0, 1]

最简单的算法就是两层循环，外层循环循环第一个整数，内层循环则在后面的数字中查找 target - num1 的结果，时间复杂度其实还是O(n^2)

改进

题目需求已经说清楚，每种输入只会对应一个答案，也就是说，我们不需要考虑数组中出现重复数字的情况，也不需要考虑一个数组中有多种组合的情况，因此，我们可以将【下标-值】的数组转换为对应的【值-下标】数组（哈希表）

例如对于示例输入[2, 7, 11, 15]中的第一项2来说，与target 9 的差值为7，我们可以将其放入数组temp中，将temp[2]置为0

我们可以将数组中的每个数字都进行上述转换，但是我们可以发现，我们并不是需要把所有数字都转换完毕之后才能找到结果，对于示例输入来说，我们循环到第二位数字7时，就已经找到了目标数值对

因此，这个过程很像是找朋友的过程，当有人来找朋友时，我们首先在登记簿中查找是否已经有需要这位朋友的人来过，如果找到了，则直接将登记者的信息返回，若没有找到，那么我们会把这个人的信息，以及他自己的下标进行登记，供后面的用户查找

具体代码实现如下图所示

var twoSum = function(nums, target) {
    // 登记簿
    const temp = []
    for(let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const remainNum = target - num;
      	// 查找登记簿中是否有该需求数字
        if (typeof temp[remainNum] !== 'undefined') {
            return [temp[remainNum], i]
        }
      	// 没有找到的话则将当前数字的信息在需求簿中登记
        temp[num] = i
    }
    return result
};

题目进阶

这个题目中明确规定了最后只会有一组结果，那么我们如果把这个限制条件改掉，我们所要查找的是数组中所有符合和为某个值的数值组合，题目修改为如下

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出所有和为目标值的整数数组，每个数字可以被重复使用，返回的数组中不能有重复数组

示例:

给定 nums = [2, 7, -2, 11], target = 9，因为 nums[0] + nums[1] = 2 + 7 = 9，nums[2] + nums[3] = -2 + 11 = 9,所以返回 [[2, 7], [-2, 11]]

解题思路：

将数组从小到大进行排序，然后应用双指针的思想，分别从数组开头和数组末尾对数组进行遍历循环，查找指针所指两数之和为目标值时的数字组合。

其中一个重要的部分是如何把其中重复的部分过滤掉，要么在遍历之前过滤，要么在全部遍历结束之后过滤

遍历前过滤：在指针移动时直接跳过相同的数字
遍历后过滤：找到所有数字组合后对最后结果进行过滤

很明显，遍历前过滤的方式更加节省时间和空间复杂度

let j = i + 1;
let k = nums.length - 1;
while (j < k) {
  // 因为是从小到大排列，如果前一个数字就比目标数字target更大，其和不可能等于target，
  // 而之后的循环中，j只会越来越大，其和不可能为target，因此不会再存在和为target的情况
  // 提前判断以减少循环次数
	if (nums[j] > target) {
		break
	}
	const curSum = nums[j] + nums[k]
  // 当两数之和为target时，将数值对推入结果数组
  if (curSum === target) {
    result.push([nums[j], nums[k]])
		// 跳过j、k之间所有重复的数字
    while (j < k && nums[j] === nums[j + 1]) j++
    while (j < k && nums[k] === nums[k - 1]) k--
    j++, k--
  } else if (curSum > target) {
    // 若两数之和大于target，则将较大数字的指针前移，并跳过所有重复数组
  	while (j < k && nums[k] === nums[k - 1]) k--
    k--
  } else {
    // 若两数之和小于target，则将较小数字的指针后移，并跳过所有重复数组
    while (j < k && nums[j] === nums[j + 1]) j++
    j++
  }
}

上述算法可以很容易地扩展到三数之和的算法，题面如下：

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

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

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

解题思路：

我们首先对输入数组进行排序，之后对该数组进行遍历，在每次遍历中，target就是当前数字的相反数，三数之和转换为两数之和的问题，我们只需要在当前指针之后的数组中查找和为target的数值对。最外层一次遍历结束之后，我们即可找到所有符合条件的三元组集合。

这其中，我们也需要过滤重复数组，对于最外层数据而言，因为我们已经排过序了，每次内层循环都能找到所有与当前数值和为0的二元组，因此，如果在最外层发现了重复数据，我们可以直接跳过这个数据，减少不必要的重复

具体代码如下：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
    const result = [];
    // 数组排序
    nums.sort((a, b) => a - b);
    
    for (let i = 0; i < nums.length - 2; i++) {
      	// 最外层循环，并声明之后两数之和target
        const target = -nums[i];
      	// 若当前数字nums[i]大于0，那么之后的数据中不可能存在二元组使得三数之和为0
        if (target < 0) {
            break
        }
      	// 若当前数字和前一个数字相同，那么直接跳过本次循环
        if (nums[i] === nums[i-1]) {
            continue
        }
      	// 以下为查找两数之和为target的过程，应用双指针思想进行查找
        let j = i + 1;
        let k = nums.length - 1;
        while (j < k) {
            if (nums[i] * nums[k] > 0 || nums[j] > target) {
                break
            }
            const curSum = nums[j] + nums[k]
            if (curSum === target) {
                result.push([nums[i], nums[j], nums[k]])
                
                while (j < k && nums[j] === nums[j + 1]) j++
                while (j < k && nums[k] === nums[k - 1]) k--
                j++, k--
            } else if (curSum > target) {
                while (j < k && nums[k] === nums[k - 1]) k--
                k--
            } else {
                while (j < k && nums[j] === nums[j + 1]) j++
                j++
            }
        }
        
    }
    return result
};