7. 数组中和为 0 的三个数

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

题目

给定一个包含 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]

输出：[]

提示：

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

注意

本题与 LeetCode 第 15 题 相同。

解题思路

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

• 数组中同一个数字可能出现多次，同一个数字也可能使用多次，但是最后输出解的时候，不能重复。例如 [-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;
};