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 {
7
8public:
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());
8
9 for ( int i = 0 ; i <= n-4 ; i++ )
10 {
11 for ( int j = i+1 ; j <= n-3 ; j++)
12 {
13 int head = j+1;
14 int tail = n-1;
15 int tar = target - nums[i] - nums[j];
16 while (head<tail)
17 {
18 if (nums[head]+nums[tail]==tar)
19 {
20 vector<int>tmp;
21 tmp.push_back(nums[i]);
22 tmp.push_back(nums[j]);
23 tmp.push_back(nums[head]);
24 tmp.push_back(nums[tail]);
25 se.insert(tmp);
26 head++;
27 tail--;
28 }
29 else if (nums[head]+nums[tail]<tar) head++;
30 else tail--;
31 }
32 }
33 }
34 for ( auto &it :se) res.push_back(it);
35 return res;
36
37
38 }
39
40};