15. 三数之和

🟠   🔖  数组 双指针 排序  🔗 力扣 LeetCode

题目

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

Explanation:

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.

The distinct triplets are [-1,0,1] and [-1,-1,2].

Notice that the order of the output and the order of the triplets does not matter.

Example 2:

Input: nums = [0,1,1]

Output: []

Explanation: The only possible triplet does not sum up to 0.

Example 3:

Input: nums = [0,0,0]

Output: [[0,0,0]]

Explanation: The only possible triplet sums up to 0.

Constraints:

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

题目大意

给定一个数组，要求在这个数组中找出 3 个数之和为 0 的所有组合。

解题思路

• 这一题比较麻烦的一点在于，最后输出解的时候，要求输出不重复的解。

• 数组中同一个数字可能出现多次，同一个数字也可能使用多次，但是最后输出解的时候，不能重复。例如 [-1, -1, 2] 和 [2, -1, -1]、[-1, 2, -1] 这 3 个解是重复的。

• 这就需要排序和去重，使用对撞指针寻找三数之和为 0 的组合。

• 先对数组进行排序，i 从后往前扫描，这里同样需要注意数组中存在多个重复数字的问题。i 在循环的时候和后一个数进行比较，如果相等，i 继续往前移，直到移到下一个和前一个数字不同的位置。

• j，k 两个指针开始一前一后对撞，j 从数组首位开始，k 为 i 的前一个数字，由于经过排序，所以 j < k。

• 对比三个数的和与 target 的大小，寻找三数之和为 target 的组合，移动指针时注意去重：

  • 小于 target，j 往后移动；
  • 大于 target，k 往前移动；

复杂度分析

• 时间复杂度：O(n^2)

  • 排序：nums.sort() 的时间复杂度是 O(n log n)，其中 n 是数组的长度。
  • 双指针查找：对于每个固定的数 nums[i]，双指针查找的复杂度是 O(n)（即遍历剩下的数组）。
  • 循环遍历： 外层循环遍历了 n 个元素，每次执行双指针查找的操作，时间复杂度为 O(n^2)。

• 空间复杂度：O(n)（不考虑输出结果），主要是用于存储结果和排序的空间。

  • 排序操作：排序操作占用 O(n) 的空间。
  • 结果存储：结果数组 res 最多存储 O(n^2) 个三元组，但由于题目通常要求三元组不重复，实际存储的元素较少。

代码

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function (nums) {
	nums = nums.sort((a, b) => a - b);
	const target = 0;
	let res = [];
	for (let i = nums.length - 1; i > 1; i--) {
		// 排除 i 重复的情况
		if (i === nums.length - 1 || nums[i] != nums[i + 1]) {
			let j = 0;
			let k = i - 1;
			let sum = target - nums[i];
			while (j < k) {
				if (nums[j] + nums[k] === sum) {
					res.push([nums[i], nums[j], nums[k]]);
					// 排除 j 重复的情况
					while (j < k && nums[j] === nums[j + 1]) {
						j++;
					}
					// 排除 k 重复的情况
					while (j < k && nums[k] === nums[k - 1]) {
						k--;
					}
					j++;
					k--;
				} else if (nums[j] + nums[k] < sum) {
					j++;
				} else {
					k--;
				}
			}
		}
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
1	两数之和	[✓]	数组 哈希表
16	最接近的三数之和	[✓]	数组 双指针 排序
18	四数之和	[✓]	数组 双指针 排序
259	较小的三数之和 🔒	[✓]	数组 双指针 二分查找 1+
2367	等差三元组的数目		数组 哈希表 双指针 1+
2908	元素和最小的山形三元组 I		数组
2909	元素和最小的山形三元组 II		数组