LeetCode 18. 4Sum（给定和，求四元组）

题目描述：

    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.

注意：The solution set must not contain duplicate quadruplets.

例子：

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]
]

分析：
    题意：给定一个数组S，一个目标target，返回S中所有满足a+b+c+d=target的不重复四元组(a, b, c, d)。
    思路：这道题和LeetCode 15、16采用的是完全一致的思想：双指针法。区别在于：此处需要查找四元组，因此需要增加一层循环；其它“跳过重复数字”的处理技巧保持不变。
    时间复杂度为O(nlogn)+O(n³)=O(n³)。

代码：

#include <bits/stdc++.h>

using namespace std;

class Solution {
private: 
	static int cmp(const int a, const int b){
		return a < b;
	}

public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int n = nums.size();
		vector<vector<int>> ans;
		// Exceptional Case: 
		if(n <= 3){
			return ans;
		}
		// sort
		sort(nums.begin(), nums.end(), cmp);
		int i, j, left, right;
		// two pointers
		for(i = 0; i <= n - 4;){
			for(j = i + 1; j <= n - 3;){
				left = j + 1;
				right = n - 1;
				while(left < right){
					int sum = nums[i] + nums[j] + nums[left] + nums[right];
					if(sum == target){
						vector<int> res = {nums[i], nums[j], nums[left], nums[right]};
						ans.push_back(res);
						left++;
						right--;
						while(left < right && nums[left] == nums[left - 1]){
							left++;
						}
						while(left < right && nums[right] == nums[right + 1]){
							right--;
						}						
					}
					else if(sum < target){
						left++;
						while(left < right && nums[left] == nums[left - 1]){
							left++;
						}
					}
					else if(sum > target){
						right--;
						while(left < right && nums[right] == nums[right + 1]){
							right--;
						}
					}
				}
				j++;
				while(j <= n - 3 && nums[j] == nums[j - 1]){
					j++;
				}
			}
			i++;
			while(i <= n - 4 && nums[i] == nums[i - 1]){
				i++;
			}
		}
		return ans;
    }
};