# 题目列表

# 三数之和

题目链接🔗

用这个 nums 数组举例。首先数组排序，然后有一层 for 循环， i 从下标 0 的地方开始，同时定一个下标 left 定义在 i+1 的位置上，定义下标 right 在数组结尾的位置上。

依然还是在数组中找到 abc 使得 $a + b +c =0$ ，我们这里相当于 a = nums[i]，b = nums[left]，c = nums[right] 。

接下来移动 left 和 right :

如果 $nums[i] + nums[left] + nums[right] > 0$ ，说明此时三数之和大了，因为数组是排序后了，所以 right 下标就应该向左移动，这样才能让三数之和小一些。
如果 $nums[i] + nums[left] + nums[right] < 0$ ，说明此时三数之和小了， left 就向右移动，才能让三数之和大一些。
直到 left 与 right 相遇为止。

a 是 nums 里遍历的元素，如果重复应该直接跳过去。

我们要的是不能由重复的三元组，但三元组内的元素是可以重复的。

b 和 c 只需要考虑指针移动到下一个位置的元素是否与当前位置元素相同。

并且去重应放在找到一个三元组之后

	while (right > left && nums[right] == nums[right - 1]) right--;
	while (right > left && nums[left] == nums[left + 1]) left++;

	class Solution {
	public:
	vector<vector<int>> threeSum(vector<int>& nums) {
	vector<vector<int>> result;
	sort(nums.begin(), nums.end());
	// 找出 a + b + c = 0
	// a = nums[i], b = nums[left], c = nums[right]
	for (int i = 0; i < nums.size(); i++) {
	// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
	if (nums[i] > 0) {
	break;
	}
	// 去重 a
	if (i > 0 && nums[i] == nums[i - 1]) {
	continue;
	}
	int left = i + 1;
	int right = nums.size() - 1;
	while (right > left) {
	// 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
	/*
	while (right > left && nums[right] == nums[right - 1]) right--;
	while (right > left && nums[left] == nums[left + 1]) left++;
	*/
	if (nums[i] + nums[left] + nums[right] > 0) right--;
	else if (nums[i] + nums[left] + nums[right] < 0) left++;
	else {
	result.push_back(vector<int>{nums[i], nums[left], nums[right]});
	// 去重逻辑应该放在找到一个三元组之后，对 b 和 c 去重
	while (right > left && nums[right] == nums[right - 1]) right--;
	while (right > left && nums[left] == nums[left + 1]) left++;
	// 找到答案时，双指针同时收缩
	right--;
	left++;
	}
	}
	}
	return result;
	}
	};

题目链接🔗

思路和三数之和一致，在三数之和基础上再加一层 for 循环。

三数之和是一层 for 循环的 nums[i] 为确定值，而四数之和是两层 for 循环的 nums[i] + nums[k] 为确定值。

	class Solution {
	public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
	vector<vector<int>> result;
	sort(nums.begin(), nums.end());
	for (int k = 0; k < nums.size(); k++) {
	// 剪枝处理
	if (nums[k] > target && nums[k] >= 0) {
	break; // 这里使用 break，统一通过最后的 return 返回
	}
	// 对 nums [k] 去重
	if (k > 0 && nums[k] == nums[k - 1]) {
	continue;
	}
	for (int i = k + 1; i < nums.size(); i++) {
	// 2 级剪枝处理
	if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
	break;
	}

	// 对 nums [i] 去重
	if (i > k + 1 && nums[i] == nums[i - 1]) {
	continue;
	}
	int left = i + 1;
	int right = nums.size() - 1;
	while (right > left) {
	//nums [k] + nums [i] + nums [left] + nums [right] > target 会溢出
	if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {
	right--;
	//nums [k] + nums [i] + nums [left] + nums [right] < target 会溢出
	} else if ((long) nums[k] + nums[i] + nums[left] + nums[right] < target) {
	left++;
	} else {
	result.push_back(vector<int>{nums[k], nums[i], nums[left], nums[right]});
	// 对 nums [left] 和 nums [right] 去重
	while (right > left && nums[right] == nums[right - 1]) right--;
	while (right > left && nums[left] == nums[left + 1]) left++;

	// 找到答案时，双指针同时收缩
	right--;
	left++;
	}
	}

	}
	}
	return result;
	}
	};