跳到主要内容

15. 三数之和

题目描述​

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例 1：：

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

输出：[[-1,-1,2],[-1,0,1]]

解释：

nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0

nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0

nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0

不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。

注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]

输出：[]

解释：唯一可能的三元组和不为 0 。

示例 3：

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

输出：[[0,0,0]]

解释：唯一可能的三元组和为 0 。

提示：

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

出处：LeetCode

解法一：排序 + 双指针​

思路​

可以先对数组进行排序，然后使用双指针枚举所有的两个元素，判断第三个元素是否存在。

代码​

function threeSum(nums: number[]): number[][] {
  const n = nums.length;
  nums.sort((a, b) => a - b);
  const res: number[][] = [];
  for (let i = 0; i < n; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    let k = n - 1;
    for (let j = i + 1; j < n; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      while (j < k && nums[i] + nums[j] + nums[k] > 0) k--;
      if (j === k) break;
      if (nums[i] + nums[j] + nums[k] === 0) res.push([nums[i], nums[j], nums[k]]);
    }
  }
  return res;
}

复杂度分析​

  • 时间复杂度：O(n2)O(n^2)，其中 nn 是数组的长度。
  • 空间复杂度：O(log⁡n)O(\log n)。

解法二：哈希表​

思路​

可以先将数组中的元素存储到哈希表中，然后使用两层循环枚举所有的两个元素，判断第三个元素是否存在于哈希表中。

代码​

function threeSum(nums: number[]): number[][] {
  const n = nums.length;
  nums.sort((a, b) => a - b);
  const res: number[][] = [];
  const map = new Map<number, number>();
  for (let i = 0; i < n; i++) {
    map.set(nums[i], i);
  }
  for (let i = 0; i < n; i++) {
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    for (let j = i + 1; j < n; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue;
      const k = map.get(-nums[i] - nums[j]);
      if (k !== undefined && k > j) {
        res.push([nums[i], nums[j], nums[k]]);
      }
    }
  }
  return res;
}

复杂度分析​

  • 时间复杂度：O(n2)O(n^2)，其中 nn 是数组的长度。
  • 空间复杂度：O(n)O(n)。