【LeetCode】Day127-四数之和 & 组合总和

题目1、四数之和

18. 四数之和【中等】

题解

从力扣第一题的两数之和，进阶到三数之和，现在到了四数之和

仍然可以沿用双指针的方法，先对数组进行排序，然后用两重循环枚举前两个数，双指针枚举后两个数
还需要注意的一个问题是，四数之和有可能会超出int界限，所以sum要用long型整数表示，其他的就和三数之和一样了

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>>res=new ArrayList<>();
        Arrays.sort(nums);
        int n=nums.length;
        if(n<4)
            return res;
        for(int i=0;i<n;i++){
            if(i+3<n&&(long)nums[i]+nums[i+1]+nums[i+2]+nums[i+3]>target)//剪枝
                break;
            for(int j=i+1;j<n;j++){
                int L=j+1,R=n-1;
                while(L<R){
                    long sum=(long)nums[i]+nums[j]+nums[L]+nums[R];
                    if(sum==target){
                        res.add(Arrays.asList(nums[i],nums[j],nums[L],nums[R]));
                        while(L+1<R&&nums[L+1]==nums[L])
                            L++;
                        while(R-1>L&&nums[R-1]==nums[R])
                            R--;
                        L++;
                        R--;
                    }
                    else if(sum<target)
                        L++;
                    else
                        R--;
                }
                while(j+1<n&&nums[j+1]==nums[j])
                    j++;
            }
            while(i+1<n&&nums[i+1]==nums[i])
                    i++;
        }
        return res;
    }
}
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

时间复杂度：$O(n^3)$

空间复杂度：$O(logn)$，排序所需的时间复杂度

题目2、组合总和

39. 组合总和【中等】

题解

和上一题有点像，不过这题中同一个数字可以被无限次选取，给题目增加了难度

对于这类寻找所有可行解的题，我们都可以尝试用「搜索回溯」的方法来解决。

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>>res=new ArrayList<>();
        List<Integer>combine=new ArrayList<>();
        dfs(candidates,target,0,res,combine);
        return res;
    }
    public void dfs(int[] candidates,int target,int idx,List<List<Integer>>res,List<Integer>combine){
        if(idx==candidates.length)
            return;
        if(target==0){
            res.add(new ArrayList<Integer>(combine));
            return;
        }
        //跳过
        dfs(candidates,target,idx+1,res,combine);
        //选择该数
        if(target-candidates[idx]>=0){
            combine.add(candidates[idx]);
            //由于每一个元素可以重复使用，下一轮搜索的起点依然是idx
            dfs(candidates,target-candidates[idx],idx,res,combine);
            combine.remove(combine.size()-1);//回溯
        }
    }
}
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

时间复杂度：$O(S)$，其中 S 为所有可行解的长度之和。

空间复杂度：$O(target)$，递归栈的深度，最深为target层。