Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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:
9
10 vector<vector<int> >res;
11 set<vector<int> >se;
12 int n;
13 vector<vector<int>> fourSum(vector<int>& nums, int target) {
14 n = nums.size();
15 if (n<4) return res;
16 sort(nums.begin(),nums.end());
17
18 for ( int i = 0 ; i <= n-4 ; i++ )
19 {
20 for ( int j = i+1 ; j <= n-3 ; j++)
21 {
22 int head = j+1;
23 int tail = n-1;
24 int tar = target - nums[i] - nums[j];
25 while (head<tail)
26 {
27 if (nums[head]+nums[tail]==tar)
28 {
29 vector<int>tmp;
30 tmp.push_back(nums[i]);
31 tmp.push_back(nums[j]);
32 tmp.push_back(nums[head]);
33 tmp.push_back(nums[tail]);
34 se.insert(tmp);
35 head++;
36 tail--;
37 }
38 else if (nums[head]+nums[tail]<tar) head++;
39 else tail--;
40 }
41 }
42 }
43 for ( auto &it :se) res.push_back(it);
44 return res;
45
46
47 }
48
49};