四数之和（18）

题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意

答案中不可以包含重复的四元组。

示例

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：

[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

算法

双指针+排序

先排序，然后双层循环确定前两个数，内层使用双指针，左指针指向第二层循环后第一个数，右指针指向最后一个数字

当指针滑动和循环数字时，遇到重复的数字应该跳过

export const fourSum = (nums, target) => {
	nums.sort((a, b) => a - b);
	let res = [];
	for (let i = 0; i < nums.length - 3; i++) {
		for (let j = i + 1; j < nums.length - 2; j++) {
			let l = j + 1,
				r = nums.length - 1;
			while (l < r) {
				if (nums[i] + nums[j] + nums[l] + nums[r] === target) {
					res.push([nums[i], nums[j], nums[l], nums[r]]);
				}
				if (nums[i] + nums[j] + nums[l] + nums[r] > target) {
					r--;
					while (nums[r] === nums[r + 1] && l < r) r--;
				} else {
					l++;
					while (nums[l] === nums[l - 1] && l < r) l++;
				}
			}
			while (nums[j] === nums[j + 1] && j < nums.length - 2) j++;
		}
		while (nums[i] === nums[i + 1] && i < nums.length - 3) i++;
	}
	return res;
};