3-23 15. 三数之和 (重点)

Date：2022-03-22 07:53:57

标签：

双指针
排序加双指针可以跳过重复项目

前置题目：

1. 两数之和 ( 简单😄 )

题目：15. 三数之和 ( 中等😕 ) (重点)

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

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

示例

示例1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

示例2：

输入：nums = []
输出：[]

示例3：

输入：nums = [0]
输出：[]

特别考虑nums中存在重复元素

分析

暴力枚举
三层for循环，枚举a,b,c的情况，使其满足条件。
重点在于通过排序，避免重复项
O(n^3), O(1)
双指针
每次枚举一个元素 a，右侧就形成了一个区间，问题就转化为了求两个数之和为 -a 的问题。
重点在于通过排序，避免重复项。
O(n^2), O(n)空间上使用了nums数组进行排序

题解

暴力枚举

function threeSum(nums: number[]): number[][] {
  const len = nums.length
  const answer: number[][] = []

  nums.sort((a, b) => a - b)

  for (let i = 0; i < len; ++i) {
    if (i > 0 && nums[i] == nums[i - 1]) {
      continue
    }

    for (let j = i + 1; j < len; ++j) {
      if (j > i + 1 && nums[j] == nums[j - 1]) {
        continue
      }

      for (let k = j + 1; k < len; ++k) {
        if (k > j + 1 && nums[k] == nums[k - 1]) {
          continue
        }

        if (nums[i] + nums[j] + nums[k] == 0) {
          answer.push([nums[i], nums[j], nums[k]])
        }
      }
    }
  }

  return answer
}

双指针

function threeSum111(nums: number[]): number[][] {
  nums.sort((a, b) => a - b)

  const len = nums.length
  const answer: number[][] = []

  for (let i = 0; i < len; ++i) {
    if (i > 0 && nums[i] == nums[i - 1]) {
      continue
    }

    let left = i + 1,
        right = len - 1,
        target = -nums[i]

    twoSum(nums, left, right, target, answer)
  }

  return answer

  function twoSum(nums: number[], left: number, right: number, target: number, answer: number[][]) {
    while (left < right) {
      const sum = nums[left] + nums[right]
      if (sum == target) {
        answer.push([-target, nums[left], nums[right]])

        left++
        right--

        // must compare with previous number (left -1)
        while (left > 0 && left < right && nums[left] == nums[left - 1]) {
          left++
        }
        while (right < len - 1 && left < right && nums[right] == nums[right + 1]) {
          right--
        }
      } else if (sum < target) {
        left++
      } else {
        right--
      }
    }
  }
}

使用

function main() {
  // const nums = [-1, 0, 1, 2, -1, -4]
  // const nums = [0, 0, 0, 0, 0]
  // const nums = [0, 0]
  // const nums = [-1, 1, -1, 1]
  const nums = [-2, 0, 1, 1, 2]

  console.log('[]:', threeSum(nums))
  console.log('[]:', threeSum111(nums))
}

main()

export {}

扩展1：两数之和

题目：1. 两数之和 ( 简单😄 )

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例