三数之和（15）

题目

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

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

示例

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：[[-1, 0, 1], [-1, -1, 2]]

算法

• 对数组排序
• 指定一个数字nums[i]，从数组第一项开始递增
• 指定左指针和右指针，左指针l指向nums[i+1]，右指针r指向nums[length-1]
• 滑动两个指针，使得nums[i]+nums[l]+nums[r]===0，滑动规则：
  • 三数之和大于0，右指针r--
  • 三数之和小于0，左指针l++
  • 三数之和等于0，推入结果数组，同时左右指针同时滑动，如果左右指针指向的下一个数字相同，则需要跳过（去重）
  • 左右指针滑动的结束条件：左指针大于等于右指针
• 让基准数字nums[i]指向下一个数字，如果nums[i+1]===nums[i]，则跳过该数字（继续i++）
• 如果nums[i]大于0，则三数之和必大于0（nums[l],nums[r]都大于nums[i]），则停止移动i指针，输出结果

function threeSum(nums) {
	nums.sort((a, b) => a - b);
	let i = 0;
	let res = [];
	while (nums[i] <= 0 && i < nums.length) {
		let l = i + 1;
		let r = nums.length - 1;
		while (l < r) {
			if (nums[i] + nums[l] + nums[r] === 0) {
				res.push([nums[i], nums[l], nums[r]]);
				while (nums[l + 1] === nums[l] && l < r) l++;
				while (nums[r - 1] === nums[r] && l < r) r--;
				l++;
				r--;
			} else if (nums[i] + nums[l] + nums[r] > 0) {
				r--;
			} else {
				l++;
			}
		}
		do {
			i++;
		} while (nums[i] === nums[i - 1]);
	}
  return res;
}