LeetCode 18. 4Sum

LeetCode 18. 4Sum

Description:

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

Example:
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]

---

分析：

首先，判断数组长度，若小于4，直接返回空二维vector；
将数组按从小到大排序，先确定nums[i]为第一个元素，nums[j]为第二个元素，为了避免重复，如果nums[i]和nums[i-1]相等就continue，如果nums[j]和nums[j-1]相等就continue，然后设定两个变量begin和end，begin指向j+1，end指向n-1；
判断此时sum是否等于target，如果等于target就将nums[i]，nums[j]，nums[begin]，nums[end]放入result数组中，且begin++，end--，为了避免重复，如果begin++后的元素依旧和刚才的元素相等，继续begin++，end同理
如果sum大于target，则end--；若果sum小于target，就将begin++；
最后返回result二维数组。

代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
	vector<vector<int> > fourSum(vector<int>& nums, int target) {
		vector<vector<int> > result;
		int n = nums.size();
		if (n < 4) return result;
		sort(nums.begin(), nums.end());
		vector<int> temp(4);
		for (int i = 0; i < n - 3; i++) {
			if (i > 0 && nums[i] == nums[i - 1]) continue;
			for (int j = i + 1; j < n - 2; j++) {
				if (j > i + 1 && nums[j] == nums[j - 1]) continue;
				int begin = j + 1, end = n - 1;
				while (begin < end) {
					int sum = nums[i] + nums[j] + nums[begin] + nums[end];
					if (sum == target) {
						temp[0] = nums[i];
						temp[1] = nums[j];
						temp[2] = nums[begin];
						temp[3] = nums[end];
						result.push_back(temp);
						begin++;
						end--;
						while (begin < end && nums[begin] == nums[begin - 1]) begin++;
						while (begin < end && nums[end] == nums[end + 1]) end--;
					}
					else if (sum > target) {
						end--;
					}
					else {
						begin++;
					}
				}
			}
		}
		return result;
	}
};
int main() {
	int n;
	cin >> n;
	vector<int> nums;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		nums.push_back(t);
	}
	int target;
	cin >> target;
	Solution s;
	vector<vector<int> > result = s.fourSum(nums, target);
	for (int i = 0; i < result.size(); i++) {
		for (int j = 0; j < result[i].size(); j++) {
			cout << result[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}