-
Notifications
You must be signed in to change notification settings - Fork 0
/
4Sum
31 lines (31 loc) · 1020 Bytes
/
4Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
sort(nums.begin(), nums.end());
set<vector<int>> set;
vector<vector<int>> output;
for(int i=0; i<n-3; i++){
for(int j=i+1; j<n-2; j++){
long long newTarget = (long long)target - (long long)nums[i] - (long long)nums[j];
int low = j+1, high = n-1;
while(low < high){
if(nums[low] + nums[high] < newTarget){
low++;
}
else if(nums[low] + nums[high] > newTarget){
high--;
}
else{
set.insert({nums[i], nums[j], nums[low], nums[high]});
low++; high--;
}
}
}
}
for(auto it : set){
output.push_back(it);
}
return output;
}
};