双指针

两数之和 II - 输入有序数组

const twoSum = function (numbers, target) {
  let l = 0
  let r = numbers.length - 1
  while (true) {
    const s = numbers[l] + numbers[r]
    if (s === target) return [l + 1, r + 1]
    s > target ? r-- : l++
  }
}

数组已经是排好序的,使用双指针遍历,如果大于目标值,则右指针左移,如果小于目标值,则左指针右移.题目肯定存在一个答案,所以使用 while(true).

三数之和

根据上面两数之和的思路,这道题可以转化为两数之和.nums[i] + nums[j] === -nums[k].返回结果的顺序不重要,所以我们可以规定 x < l < r. 不能包括重复的三元组,所以每次遍历的时候都和它的后面一个比较一下是否相等,相等跳过.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
const threeSum = function (nums) {
  nums.sort((a, b) => a - b)
  const ans = []
  const length = nums.length
  for (let i = 0; i < length - 2; i++) {
    const x = nums[i]
    if (i > 0 && x === nums[i - 1]) continue // 跳过重复数字
    if (x + nums[i + 1] + nums[i + 2] > 0) break // 优化一
    if (x + nums[length - 2] + nums[length - 1] < 0) continue // 优化二

    let l = i + 1
    let r = length - 1

    while (l < r) {
      const sum = nums[l] + nums[r] + x
      if (sum > 0) {
        r--
      } else if (sum < 0) {
        l++
      } else {
        ans.push([x, nums[l], nums[r]])
        for (l++; l < r && nums[l] === nums[l - 1]; l++); // 跳过重复数字
        for (r--; l < r && nums[r] === nums[r + 1]; r--); // 跳过重复数字
      }
    }
  }
  return ans
}

参考

• 两数之和 三数之和