双指针简化数组查找
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
思路：
经过之前的「两数之和」、「三数之和」给我们的启示，对于有序数组最内层的两数循环可以用双指针法从 O(n²) 复杂度降为 O(n)。其他层的优化不会降低复杂度，所以对于「四数之和」，复杂度最少为 O(n³）。
首先我们先将原数组排序，然后记四个数的指针从小到大依次为 l1，l2，r1，r2。我们以 l1 为基准，遍历整个数组，为了防止重复，每次更新 l1 时判断与旧值是否相等，若相等则直接跳过；其次以 d 为基准，从后往前遍历 l1 的右侧部分，同样为了防止重复，更新 r2 时需要与 l1 联合判断与前一组旧值是否完全相同；最后用双指针法，以 l2、r1 从两侧向中间遍历 l1、r2 之间的部分，同样为了防止重复，每次更新 两指针时需要将 4 个指针对应的值与旧值作比较，若完全相同则跳过。
这样遍历后即可不重复不遗漏地添加所有满足要求的数组。
时间复杂度：O(n³)
空间复杂度：O(n)
实现：
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
| class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> ret = new LinkedList<>();
int len = nums.length;
int l1 = 0;
int sum;
int la = Integer.MIN_VALUE, lb = Integer.MIN_VALUE, lc = Integer.MAX_VALUE, ld = Integer.MAX_VALUE;
int a, b, c, d;
while (l1 < len - 3) {
a = nums[l1];
if (a == la) {
l1++;
continue;
}
int r2 = len - 1;
while (l1 < r2 - 2) {
d = nums[r2];
if (a == la && d == ld) {
r2--;
continue;
}
int l2 = l1 + 1, r1 = r2 - 1;
while (l2 < r1) {
b = nums[l2];
c = nums[r1];
if (a == la && b == lb && c == lc && d == ld) {
r1--;
l2++;
continue;
}
sum = a + b + c + d;
if (sum > target) {
r1--;
} else if (sum < target) {
l2++;
} else {
ret.add(Arrays.asList(a, b, c, d));
la = a;
lb = b;
lc = c;
ld = d;
r1--;
l2++;
}
}
r2--;
}
l1++;
}
return ret;
}
}
|
