18. 四数之和

[MyLinChi]

题目描述

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

链接：https://leetcode-cn.com/problems/4sum

方案

固定前两个数，后两个数用双指针法。此题与三个数的和类似#7。

class Solution {
public:
	void fastsort(vector<int>& nums, int a, int b){
		if (a >= b || nums.size() <= 1)return;
		int i, j, tmp = nums[a];
		for (i = a, j = b; i < j;){
			while (i<j && nums[j] >= tmp)j--;
			nums[i] = nums[j];
			while (i < j&&nums[i] <= tmp)i++;
			nums[j] = nums[i];
		}
		nums[j] = tmp;
		fastsort(nums, a, j - 1);
		fastsort(nums, j + 1, b);
	}
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
		fastsort(nums, 0, nums.size() - 1);
		int a, b, c, d;
		int len = nums.size();
		vector<vector<int>> res = {};
		for (a = 0; a + 3<len;){
			for (b = a + 1; b + 2<len;){
				c = b + 1;
				d = len - 1;
				while (c<d){
					if ((nums[a] + nums[b] + nums[c] + nums[d])<target){
						c++;
					}
					else if ((nums[a] + nums[b] + nums[c] + nums[d])>target){
						d--;
					}
					else{
						res.push_back({ nums[a], nums[b], nums[c], nums[d] });
						int ctmp = nums[c], dtmp = nums[d];
						do{
							c++;
						} while (c<d&&nums[c] == ctmp);
						do{
							d--;
						} while (c<d&&nums[d] == dtmp);
					}
				}
				do{
					b++;
				} while (b + 2<len&&nums[b]==nums[b-1]);
			}
			do{
				a++;
			} while (a + 3<len&&nums[a]==nums[a-1]);
		}
		return res;
	}
};