leetcode 18. 4Sum (k-sum问题，two pointer)
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.
思路： O(n^2)枚举两个元素，变成2-sum问题，总体复杂度O(n^3)
hash的解法以后补
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月13日 星期四 17时24分54秒
4File Name :18.cpp
5************************************************ */
6class Solution {
public:
1 vector<vector<int> >res;
2 set<vector<int> >se;
3 int n;
4 vector<vector<int>> fourSum(vector<int>& nums, int target) {
5 n = nums.size();
6 if (n<4) return res;
7 sort(nums.begin(),nums.end());
1 for ( int i = 0 ; i <= n-4 ; i++ )
2 {
3 for ( int j = i+1 ; j <= n-3 ; j++)
4 {
5 int head = j+1;
6 int tail = n-1;
7 int tar = target - nums[i] - nums[j];
8 while (head<tail)
9 {
10 if (nums[head]+nums[tail]==tar)
11 {
12 vector<int>tmp;
13 tmp.push_back(nums[i]);
14 tmp.push_back(nums[j]);
15 tmp.push_back(nums[head]);
16 tmp.push_back(nums[tail]);
17 se.insert(tmp);
18 head++;
19 tail--;
20 }
21 else if (nums[head]+nums[tail]<tar) head++;
22 else tail--;
23 }
24 }
25 }
26 for ( auto &it :se) res.push_back(it);
27 return res;
}
};