文章目录
1.三数之和1.1.题目描述1.2.题目示例1.3.思路及代码
2.四数之和2.1题目描述2.2题目示例2.3思路及代码
1.三数之和
1.1.题目描述
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
1.2.题目示例
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
1.3.思路及代码
思路首先看到这题，可以想到的是用三重循环，那么问题来了，我们怎么解决重复，想到重复，可以想到最简单的就是set了，我们来试试这个代码如何
class Solution {
public List
<List
<Integer>> threeSum(int[] nums
) {
Set ans
= new HashSet();
for(int i
= 0; i
< nums
.length
; i
++){
for(int j
= i
+ 1; j
< nums
.length
; j
++){
for(int k
= j
+ 1; k
< nums
.length
; k
++){
if(nums
[i
] + nums
[j
] + nums
[k
] == 0){
List
<Integer> res
= new ArrayList<>();
res
.add(nums
[i
]);
res
.add(nums
[j
]);
res
.add(nums
[k
]);
Collections
.sort(res
);
ans
.add(res
);
}
}
}
}
return new ArrayList<>(ans
);
}
}
不出意外，肯定超时了，如果能解决，这题也不叫中等题了，那么如何优化？如果我们做过两数之和这题也可以这么改造，不就是c求a+b+c==0吗，因此就是求a+b和-c是否相等就好了,但是这样也不行，会有一些致命的错误既然要去重，我们可以想到肯定是没有重复元素的，那么我们可以先排序吗，如果前后元素相等我们就跳过就好了解题思路：排序+双指针
确定第一个元素时，如果它已经比 0 大了，那么可以直接跳出循环，因为后面的数字都比它大。如 [1, 2, 3, 4], i = 0, nums[i] > 0, 这样是不可能产生合法的情况的，直接 break。确定第一个元素时，如果发现它与它前面的值一样，那么跳过本轮。如 [-1, -1, 0, 1], 在第一轮后，已经选出了 {-1, 0, 1}, 现在 i = 1，nums[i] == nums[i - 1], 为了避免重复，直接 continue。接下来利用双指针，left 指向 i + 1, right 指向 nums.length - 1。逐个进行判断，并注意去重。代码都有注释，应该非常好懂！
class Solution {
public List
<List
<Integer>> threeSum(int[] nums
) {
Arrays
.sort(nums
);
List
<List
<Integer>> res
= new ArrayList<>();
for(int i
= 0; i
< nums
.length
- 2; i
++){
if(nums
[i
] > 0){
break;
}
if(i
> 0 && nums
[i
] == nums
[i
- 1]){
continue;
}
int l
= i
+ 1;
int r
= nums
.length
- 1;
while(l
< r
){
if(nums
[l
] + nums
[r
] + nums
[i
] < 0){
l
++;
}else if(nums
[l
] + nums
[r
] + nums
[i
] > 0){
r
--;
}else{
res
.add(Arrays
.asList(nums
[i
], nums
[l
], nums
[r
]));
l
++;
r
--;
while(l
< r
&& nums
[l
] == nums
[l
- 1]){
l
++;
}
while(l
< r
&& r
!= nums
.length
- 1 && nums
[r
] == nums
[r
+ 1]){
r
--;
}
}
}
}
return res
;
}
}
2.四数之和
2.1题目描述
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
2.2题目示例
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
2.3思路及代码
上面如果搞懂了三数之和，那么四数之和也会非常的简单思路和三数之和几乎一模一样只不过要在最外面要加上一个循环，仅此而已看代码
class Solution {
public List
<List
<Integer>> fourSum(int[] nums
, int target
) {
Arrays
.sort(nums
);
List
<List
<Integer>> res
= new ArrayList<>();
if(nums
== null
|| nums
.length
<= 3){
return res
;
}
for(int i
= 0; i
< nums
.length
- 3; i
++){
if(i
> 0 && nums
[i
] == nums
[i
- 1]){
continue;
}
for(int j
= i
+ 1; j
< nums
.length
- 2; j
++){
if(j
> i
+ 1 && nums
[j
] == nums
[j
- 1]){
continue;
}
int l
= j
+ 1;
int r
= nums
.length
- 1;
while(l
< r
){
if(nums
[i
] + nums
[j
] + nums
[l
] + nums
[r
] < target
){
l
++;
}else if(nums
[i
] + nums
[j
] + nums
[l
] + nums
[r
] > target
){
r
--;
}else{
res
.add(Arrays
.asList(nums
[i
], nums
[j
], nums
[l
], nums
[r
]));
l
++;
r
--;
while(l
< r
&& nums
[l
] == nums
[l
- 1]){
l
++;
}
while(l
< r
&& l
!= nums
.length
- 1 && nums
[r
] == nums
[r
+ 1]){
r
--;
}
}
}
}
}
return res
;
}
}
