leetcode 15. 三数之和

[xxleyi]

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

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

示例：

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解：此题比较直接易懂的方法是排序+分情况+双指针，然后还要有一个可靠的方法去重。

「循环不变式」的部分集中在双指针的使用过程中，小心维护，不犯错。

var threeSum = function(nums) {
  const sortedNums = nums.map(e => e).sort((a, b) => a - b)
  const zeroPart = []
  const positivePart = []
  const negativePart = []
  for (let e of sortedNums) {
    if (e < 0) negativePart.push(e)
    else if (e === 0) zeroPart.push(e)
    else positivePart.push(e)
  }
  
  const ans = []
  const done = {}

  // [zero, zero, zero] case
  if (zeroPart.length >= 3) ans.push([0, 0, 0])

  // [negative, zero, positive] case
  if (zeroPart.length >= 1) {
    let i = 0, j = positivePart.length - 1
    while (i < negativePart.length && j >= 0) {
      const [negative, positive] = [negativePart[i], positivePart[j]]
      if (negative + positive === 0) {
        if (!([negative, 0, positive] in done)) {
          ans.push([negative, 0, positive])
          done[[negative, 0, positive]] = true
        }
      i++
      j--
      } else if (negative + positive > 0) j--
      else i++
    }
  }

  // [negative, negative, positive] case
  for (let e of (new Set(positivePart))) {
    const sum = -e
    let i = 0, j = negativePart.length - 1
    while (i < j) {
      const [n1, n2] = [negativePart[i], negativePart[j]]
      if (n1 + n2 === sum) {
        if (!([n1, n2, e] in done)) {
          ans.push([n1, n2, e])
          done[[n1, n2, e]] = true
        }
        i++
        j--
      } else if (n1 + n2 > sum) j--
      else i++
    }
  }

  // [negative, positive, positive] case
  for (let e of (new Set(negativePart))) {
    const sum = -e
    let i = 0, j = positivePart.length - 1
    while (i < j) {
      const [p1, p2] = [positivePart[i], positivePart[j]]
      if (p1 + p2 === sum) {
        if (!([e, p1, p2] in done)) {
          ans.push([e, p1, p2])
          done[[e, p1, p2]] = true
        }
        i++
        j--
      } else if (p1 + p2 > sum) j--
      else i++
    }
  }

  return ans
};

上面这个方式蛮笨拙的，但算法复杂度也还行。其实，既然已经排了序，也想到了双指针，是可以直接两层循环搞定的：

• 外层从头扫到倒数第三
• 内层双指针碰头，并注意去重

var threeSum = function(nums) {
  nums = nums.map(e => e).sort((a, b) => a - b)
  const ans = []
  let i = 0
  // 外层循环
  while (i < nums.length - 2) {
    // 外层去重
    while (nums[i] === nums[i - 1]) i++
    // 内层双指针
    let left = i + 1, right = nums.length - 1
    const sum = 0 - nums[i]
    while (left < right) {
      const [l, r] = [nums[left], nums[right]]
      if (l + r === sum) {
        ans.push([nums[i], l, r])
        // 双指针去重并移动
        while (nums[left + 1] === nums[left]) left++
        left++
        while (nums[right - 1] === nums[right]) right--
        right--
      } else if (l + r < sum) left++
      else right--
    }
    // 进入下一个外层循环
    i++
  }

  return ans
}

最后，作为彩蛋，奉上函数迭代式（循环不变式呼之欲出） 实现：

// 函数式编程迭代
var threeSum = function(nums) {
  // 复制（避免修改入参）并排序
  nums = nums.map(e => e).sort((a, b) => a - b)

  // 外层从左到右迭代到倒数第三个元素
  function outer_iter(i, ans) {
    return i >= nums.length - 2
           ? ans
           : nums[i] === nums[i - 1]
             ? outer_iter(i + 1, ans)
             : outer_iter(i + 1, 
                          ans.concat(inner_iter(nums[i], i + 1, nums.length - 1, [])))
  }

  // 内层双指针迭代
  function inner_iter(e, left, right, ans) {
    return left >= right
           ? ans
           : nums[left] + nums[right] > -e
             ? inner_iter(e, left, right - 1, ans)
             : nums[left] + nums[right] < -e
               ? inner_iter(e, left + 1, right, ans)
               : inner_iter(e, left_iter(left), right_iter(right), 
                            ans.concat([[e, nums[left], nums[right]]])) 
  }

  // 左指针迭代去重
  function left_iter(left) {
    return nums[left] !== nums[left + 1]
           ? left + 1
           : left_iter(left + 1)
  }

  // 右指针迭代去重
  function right_iter(right) {
    return nums[right] !== nums[right - 1]
           ? right - 1
           : right_iter(right - 1)
  }

  return outer_iter(0, [])
}