-
Notifications
You must be signed in to change notification settings - Fork 6
/
0018.cpp
55 lines (49 loc) · 1.58 KB
/
0018.cpp
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
49
50
51
52
53
54
55
class Solution
{
public:
vector<vector<int> > fourSum(vector<int> &nums, int target)
{
vector<vector<int> > res;
if (nums.empty())
return res;
int n = nums.size();
sort(nums.begin(), nums.end());
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
int target_2 = target - nums[j] - nums[i];
int front = j + 1;
int back = n - 1;
while (front < back)
{
int sum = nums[front] + nums[back];
if (sum < target_2)
front++;
else if (sum > target_2)
back--;
else
{
vector<int> ans(4, 0);
ans[0] = nums[i];
ans[1] = nums[j];
ans[2] = nums[front];
ans[3] = nums[back];
res.push_back(ans);
while (front < back && nums[front] == ans[2])
front++;
while (front > back && nums[back] == ans[3])
back--;
}
}
//to skip 2nd pointer duplicates
while (j + 1 < n && nums[j + 1] == nums[j])
j++;
}
//to skip 1st pointer duplicates
while (i + 1 < n && nums[i + 1] == nums[i])
i++;
}
return res;
}
};