4Sum.txt

problem：
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:

Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ? b ? c ? d)
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)
-----------------------------------------------------------------------------------------
solution：
//跟3Sum的思路一致，排序，两重循环定a，b，然后首尾两指针相向走，直到找到和为target。
//优化：每次当前num[i]如果等于前一次num[i-1]，则直接跳过这次检查。
vector<vector<int> > fourSum(vector<int> &num, int target)
{
  vector<vector<int> > ret;
	if(num.size() < 4)
		return ret;
	sort(num.begin(), num.end());
	for(int i = 0; i < num.size() - 3; i++ )
	{
		if(i > 0 && num[i] == num[i - 1])
			continue;
		for(int j = i + 1; j < num.size() - 2; j++)
		{
			if(j > i+1 && num[j] == num[j-1])
				continue;
			int r = num.size() - 1;
			for(int l = j + 1; l < r; l++)
			{
				if(l > j+1 && num[l] == num[l - 1])
					continue;
				int sum = num[i] + num[j] + num[l] + num[r];
				if(sum == target)
				{
					vector<int> tmp;
					tmp.push_back(num[i]);
					tmp.push_back(num[j]);
					tmp.push_back(num[l]);
					tmp.push_back(num[r]);
					ret.push_back(tmp);
				}
				else if(sum > target)
				{
					r--;
					l--;
				}
			}
		}
	}
	return ret;
}