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
| class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
for (int a = 0; a < n - 3; ++a) {
if (a > 0 && nums[a] == nums[a - 1]) continue;
long sum = (long) nums[a] + nums[a + 1] + nums[a + 2] + nums[a + 3];
if (sum > target) break;
sum = (long) nums[a] + nums[n - 3] + nums[n - 2] + nums[n - 1];
if (sum < target) continue;
for (int b = a + 1; b < n - 2; ++b) {
if (b > a + 1 && nums[b] == nums[b - 1]) continue;
sum = (long) nums[a] + nums[b] + nums[b + 1] + nums[b + 2];
if (sum > target) break;
sum = (long) nums[a] + nums[b] + nums[n - 2] + nums[n - 1];
if (sum < target) continue;
int c = b + 1, d = n - 1;
while (c < d) {
sum = nums[a] + nums[b] + nums[c] + nums[d];
if (sum == target) {
ans.add(List.of(nums[a], nums[b], nums[c], nums[d]));
while (c < d && nums[c] == nums[c + 1]) ++c;
while (c < d && nums[d] == nums[d - 1]) --d;
++c;
--d;
} else if (sum < target) ++c;
else --d;
}
}
}
return ans;
}
}
|
wechat
