15.三数之和.md

15.三数之和

/*
 * @lc app=leetcode.cn id=15 lang=typescript
 *
 * [15] 三数之和
 */

// @lc code=start
function threeSum(nums: number[]): number[][] {}
// @lc code=end

解法 1: 暴力解法 三层遍历

• 时间复杂度:
• 空间复杂度:

function threeSum(nums: number[]): number[][] {
  let cache: { [key: string]: number[] } = {}
  for (let i = 0; i < nums.length - 2; i++) {
    for (let j = i + 1; j < nums.length - 1; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        if (nums[i] + nums[j] + nums[k] === 0) {
          let arr = [nums[i], nums[j], nums[k]]
          let key = arr.sort((a, b) => a - b).join('')
          cache[key] = arr
        }
      }
    }
  }

  return Object.values(cache)
}

解法 2: 优化为两层遍历

• 时间复杂度:
• 空间复杂度:

function threeSum(nums: number[]): number[][] {
  let arrCache: { [key: string]: number[] } = {}
  let cache = new Set<number>()
  for (let i = 0; i < nums.length - 2; i++) {
    cache = new Set()
    let num = nums[i]
    for (let j = i + 1; j < nums.length; j++) {
      if (cache.has(-num - nums[j])) {
        let arr = [num, -num - nums[j], nums[j]]
        arrCache[[...arr].sort((a, b) => a - b).join('')] = arr
      }
      cache.add(nums[j])
    }
  }

  return Object.values(arrCache)
}

解法 3: 排序 + 双指针

• 时间复杂度:
• 空间复杂度:

在两数之和的基础上,演化而来,先对数组排序,固定左指针作为 target,然后找出右边数列中两数之和为 -target 的组合.

function threeSum(nums: number[]): number[][] {
  const n = nums.length
  nums = [...nums].sort((a, b) => a - b)
  const res: number[][] = []
  for (let i = 0; i < n; i++) {
    // 当前值和前面的值相等时,也就是重复情况,跳过
    if (nums[i] === nums[i - 1]) continue
    // 当第一个值大于 0 时,后面三数相加必大于 0,可以直接排除后面的所有情况
    if (nums[i] > 0) break

    let [left, right] = [i + 1, n - 1]
    while (left < right) {
      // 当最后一个值小于 0 时,那三数相加必小于 0,直接跳到下一个 i
      if (nums[right] < 0) break

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

      if (sum < 0) left++
      else if (sum > 0) right--
      else {
        res.push([nums[i], nums[left++], nums[right--]])
        // 排除左指针的重复情况
        while (left < right && nums[left] === nums[left - 1]) left++
        // 排除右指针的重复情况
        while (left < right && nums[right] === nums[right + 1]) right--
      }
    }
  }
  return res
}

Case

test.each([
  {
    input: { nums: [-1, 0, 1, 2, -1, -4] },
    output: [
      [-1, -1, 2],
      [-1, 0, 1],
    ],
  },
  {
    input: { nums: [-1, 0, 1, 2, -1, -4, -1, -1, 2, 2, 2, 2] },
    output: [
      [-4, 2, 2],
      [-1, -1, 2],
      [-1, 0, 1],
    ],
  },
  { input: { nums: [] }, output: [] },
  { input: { nums: [0] }, output: [] },
])('input: nums = $input.nums', ({ input: { nums }, output }) => {
  expect(threeSum(nums)).toIncludeSameMembers(output)
})