Leetcode 18-四数之和

本文主要是介绍Leetcode 18-四数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题解看代码随想录
/*
1.先排序，为了便于使用双指针，复杂度O(logN)
2.固定最小指针a,b,双指针c和d分别从0和len-1向中间移动
从两端向中间移动是为了使得两个数下标不重合，且可以将时间复杂度从双重循环的O(N^4)降到O(N3)
3.终止条件：a>N-3||nums[a]>0(此时四数之和必定大于0)
3.不可以包含重复元素：前后元素相同时跳过
*/
class Solution {
public List<List> fourSum(int[] nums, int target) {
Arrays.sort(nums);
int sum=0,c,d;
List<List> res = new ArrayList<>();
for(int a=0;a<nums.length-3;a++){
//提前终止
//不要判断nums[k] > target 就返回了，三数之和 可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[i] > target && (nums[i] >=0 || target >= 0)就可以了
if(nums[a]>target&&nums[a]>=0) break;
//对a进行去重
if(a>0&&nums[a]==nums[a-1]) continue;
for(int b=a+1;b<nums.length-2;b++){
//多判断b>a+1是为了避免在[2,2,2,2,2],target=8时没有输出
//所以不判断b=a+1的情况，即b可以等于a
if(b>a+1&&nums[b]==nums[b-1]) continue;
c=b+1;
d=nums.length-1;
while(c<d){
sum=nums[a]+nums[b]+nums[c]+nums[d];
if(sum>target){
d–;
}else if(sum<target){
c++;
}else{
res.add(Arrays.asList(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–;

                }}}}return res;
}

}

这篇关于Leetcode 18-四数之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---