Ayingotts's notes

Appearance

15-三数之和 ​

思路：

  1. 无序数组，查找目标与数值大小相关，考虑先排序降低复杂度
  2. 三数之和 = 一个数 + 两数之和
  3. 双指针
ts
function threeSum(nums: number[]): number[][] {
  if (nums.length < 3) return []

  const result = []

  // O(n * lgn)
  nums.sort((a, b) => a - b)

  for (let i = 0; i < nums.length; i++) {
    // 越过相同元素
    if (nums[i] === nums[i - 1]) continue

    // 左右指针
    let left = i + 1
    let right = nums.length - 1

    // 以 nums[i] 为基准，寻找另外两数，其和为 -nums[i]
    while (left < right) {
      if (nums[left] + nums[right] + nums[i] === 0) {
        // 命中
        result.push([nums[left], nums[right], nums[i]])

        // 左指针越过相同元素
        while (nums[left] === nums[left + 1]) {
          left += 1
        }

        // 左指针向右
        left += 1

        // 右指针越过相同元素
        while (nums[right] === nums[right - 1]) {
          right -= 1
        }

        // 右指针向左
        right -= 1
      } else if (nums[left] + nums[right] + nums[i] > 0) {
        // 和过大，右指针向左
        right -= 1
      } else {
        // 和过小，左指针向右
        left += 1
      }
    }
  }

  return result
}
function threeSum(nums: number[]): number[][] {
  if (nums.length < 3) return []

  const result = []

  // O(n * lgn)
  nums.sort((a, b) => a - b)

  for (let i = 0; i < nums.length; i++) {
    // 越过相同元素
    if (nums[i] === nums[i - 1]) continue

    // 左右指针
    let left = i + 1
    let right = nums.length - 1

    // 以 nums[i] 为基准，寻找另外两数，其和为 -nums[i]
    while (left < right) {
      if (nums[left] + nums[right] + nums[i] === 0) {
        // 命中
        result.push([nums[left], nums[right], nums[i]])

        // 左指针越过相同元素
        while (nums[left] === nums[left + 1]) {
          left += 1
        }

        // 左指针向右
        left += 1

        // 右指针越过相同元素
        while (nums[right] === nums[right - 1]) {
          right -= 1
        }

        // 右指针向左
        right -= 1
      } else if (nums[left] + nums[right] + nums[i] > 0) {
        // 和过大，右指针向左
        right -= 1
      } else {
        // 和过小，左指针向右
        left += 1
      }
    }
  }

  return result
}

总结：

  1. 有序数组比无序数组更好处理
  2. 简化处理模型：三数之和 = 一个数 + 两数之和
  3. 注意边界条件
  4. 需要去重，越过相同元素
  5. 双指针真好用