0018-四数之和.md

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

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

var fourSum = function(nums, target) {
  nums = nums.sort((a, b) => a - b)
  const len = nums.length
  const result = []
  for (let i = 0; i < len - 3; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue
    }
    for (let j = i + 1; j < len - 2; j++) {
      let l = j + 1, r = len - 1
      if (j - 1 > i && nums[j] === nums[j - 1]) {
        continue
      }
      while(l < r) {
        const sum = nums[i] + nums[j] + nums[l] + nums[r]
        if (sum === target) {
          result.push([nums[i], nums[j], nums[l], nums[r]])
          while(l < r && nums[l] === nums[l + 1]) {
            l++
          }
          while(l < r && nums[r] === nums[r - 1]) {
            r--
          }
          l++
          r--
        } else {
          sum > target ? r-- : l++
        }
      }
    }
  }
  return result
};

解题思路： 和三数之和差不多，不过相比于三数之和拥有更为复杂严密的去重判断。