Skip to content

Commit 5f45809

Browse files
JavaCodeMingJavaCodeMing
committed
Create 18.四数之和(中等).md
1 parent 50683b4 commit 5f45809

1 file changed

Lines changed: 103 additions & 0 deletions

File tree

‎Algorithm/18.四数之和(中等).md‎

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
```text
2+
题目:
3+
给定一个包含n个整数的数组 nums 和一个目标值 target,
4+
判断 nums 中是否存在四个元素 a,b,c和d,使得a+b+c+d的值与target相等?
5+
找出所有满足条件且不重复的四元组;
6+
注意: 答案中不可以包含重复的四元组;
7+
示例:
8+
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0;
9+
满足要求的四元组集合为:
10+
[
11+
[-1, 0, 0, 1],
12+
[-2, -1, 1, 2],
13+
[-2, 0, 0, 2]
14+
]
15+
1.四重暴力循环:
16+
[1]思路: 嵌套四层循环,每一层做防重处理,在最内层判断四数之和与目标值是否相同;
17+
[2]实现: 略
18+
[3]复杂度分析:
19+
(1)时间复杂度: O(N^4),其中N是数组长度
20+
(2)空间复杂度: O(1)
21+
2.两层循环+双指针遍历:
22+
[1]思路:
23+
(1)考虑要做防重,最简单的方式就是先排序,在遍历的时候与前值比较,重复则跳过;
24+
(2)在两层for循环开头需要进行防重处理: 非开始遍历则与前值判断,相等则下一个;
25+
(3)在双指针遍历中,仅对左指针做防重处理,并在出现四数之和与目标值相等时移动左指针;
26+
(在四数之和与目标值相等时,左右指针二选一移动都可(仅为打破平衡),移动哪个指针就对哪个指针做防重)
27+
(4)双指针遍历主要考虑的是两个指针的移动条件:
28+
四数之和大于目标值移动右指针,
29+
小于目标值移动左指针,
30+
等于目标值移动左指针(因为防重了)
31+
(5)最后在功能调试成功后,考虑到性能问题,在两层循环中对极端边界先处理过滤掉明显不符合的数组;
32+
[2]实现:
33+
class Solution {
34+
public List<List<Integer>> fourSum(int[] nums, int target) {
35+
int n = nums.length;
36+
//先排序为之后的防重操作做准备
37+
Arrays.sort(nums);
38+
List<List<Integer>> result = new ArrayList<>();
39+
for (int i = 0; i < n - 3; i++) {
40+
//防止第一个数出现重复
41+
if(i > 0 && nums[i] == nums[i - 1]){
42+
continue;
43+
}
44+
// 对极端边界先判断处理(最小值和最大值)
45+
int min1=nums[i]+nums[i+1]+nums[i+2]+nums[i+3];
46+
if(min1>target){
47+
break;
48+
}
49+
int max1=nums[i]+nums[n-1]+nums[n-2]+nums[n-3];
50+
if(max1<target){
51+
continue;
52+
}
53+
for (int j = i + 1; j < n - 2; j++) {
54+
//防止第二个数出现重复
55+
if(j > i+1 && nums[j] == nums[j - 1]){
56+
continue;
57+
}
58+
//双指针遍历
59+
int left = j + 1;
60+
int right = n - 1;
61+
// 对极端边界先判断处理(最小值和最大值)
62+
int min=nums[i]+nums[j]+nums[left]+nums[left+1];
63+
if(min>target){
64+
continue;
65+
}
66+
int max=nums[i]+nums[j]+nums[right]+nums[right-1];
67+
if(max<target){
68+
continue;
69+
}
70+
while (left < right) {
71+
// 防止左指针移动到重复数值上
72+
while (left > j + 1 && left < right && nums[left] == nums[left - 1]) {
73+
left++;
74+
}
75+
// 当左右指针位置相同,说明未找到四数之和等于目标值
76+
if (left == right) {
77+
break;
78+
}
79+
int temp = nums[i] + nums[j] + nums[left] + nums[right];
80+
if (temp == target) {
81+
List<Integer> list = new ArrayList<>();
82+
list.add(nums[i]);
83+
list.add(nums[j]);
84+
list.add(nums[left]);
85+
list.add(nums[right]);
86+
result.add(list);
87+
// 当相等时,移动左指针(因为在之前我只对左指针做了防重,若要移动右指针需对右指针做防重)
88+
left++;
89+
} else if (temp > target) {
90+
right--;
91+
} else {
92+
left++;
93+
}
94+
}
95+
}
96+
}
97+
return result;
98+
}
99+
}
100+
[3]复杂度分析:
101+
(1)时间复杂度: O(N^3),其中N是数组长度
102+
(2)空间复杂度: O(1)
103+
```

0 commit comments

Comments
 (0)