-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathFind All Four Sum Numbers
48 lines (39 loc) · 1.59 KB
/
Find All Four Sum Numbers
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// User function template for C++
// arr[] : int input array of integers
// k : the quadruple sum required
vector<vector<int> > fourSum(vector<int> &nums, int target) {
vector<vector<int>> result;
if(nums.empty())
return result;
sort(nums.begin(),nums.end());
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
int target_2=target-nums[i]-nums[j];
int front=j+1, back=nums.size()-1;
while(front<back){
int two_sum=nums[front]+nums[back];
if(two_sum<target_2)
front++;
else if(two_sum>target_2)
back--;
else{
vector<int> quadruplet(4, 0);
quadruplet[0] = nums[i];
quadruplet[1] = nums[j];
quadruplet[2] = nums[front];
quadruplet[3] = nums[back];
result.push_back(quadruplet);
// Processing the duplicates of number 3
while(front<back && nums[front]==quadruplet[2]) ++front;
// Processing the duplicates of number 4
while(front<back && nums[back]==quadruplet[3]) --back;
}
}
// Processing the duplicates of number 2
while(j+1<nums.size() && nums[j+1]==nums[j]) ++j;
}
// Processing the duplicates of number 1
while (i+1<nums.size() && nums[i+1]==nums[i]) ++i;
}
return result;
}