18-4Sum

题目详情

解题思路

一看这题目就是老三数之和了，不会三数之和的，可以去看看我写的题解：三数之和。

看懂三数之和了，那和这个四数之和有什么区别，无非就是多套了一层循环，把四数之和拆为一个数和三数之和。没啥好说里。

测试用例: 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

代码实现

代码实现没什么难得，时间复杂度为$O(N)$。

其中有一个可优化的点，在最外层循环中，如果：nums[i]+nums[nums.length-1]*3<target，那么可以直接跳过这层循环，处理下一个数了。因为数组是递增的，当前数与最大数的三倍之和还小于target，那么结果集中根本就不会出现以nums[i]开头的结果。

同理，如果nums[i]+3*nums[i+1]>target，可以提前终止循环了，因为数组是递增的，nums[i]都不可能构成结果，后面的数就更不用说了。

进行上述剪枝操作后，优化效果还是很明显的，但是不知道为什么在求三数之和时进行上述剪枝后时间反而还变长了...无语。

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result=new ArrayList<>();
        if(nums== null || nums.length<4){
            return result;
        }
        Arrays.sort(nums);
        //最外层循环
        for(int i=0;i+4<=nums.length;i++){

            if(i-1>-1 && nums[i-1]==nums[i]){
                continue;
            }
            //进行剪枝优化
            if((nums[i]+3*nums[nums.length-1])<target){
                continue;
            }
            if((nums[i]+3*nums[i+1])>target){
                break;
            }
            getThreeSum(target-nums[i],nums,i+1,nums[i],result);
        }
        return result;

    }

    //在nums中从begin开始，找到三数之和为target的组合
    private void getThreeSum(int target,int[] nums,int begin,int curNum,List<List<Integer>> result){
        if(begin+3>nums.length){
            return;
        }
        int left=0;
        int right=0;
        int curTarget=0;
        for(int i=begin;i+3<=nums.length;i++){
            if(i-1>=begin && nums[i-1]== nums[i]){
                continue;
            }
            curTarget=target-nums[i];
            left=i+1;
            right=nums.length-1;
            while(left<right){
                //指定指针移动的规则
                if(nums[left]+nums[right]<curTarget){
                    left++;
                }
                else if(nums[left]+nums[right]>curTarget){
                    right--;
                }
                //可以放入结果了
                else{
                    if(left-1>i && nums[left-1]== nums[left]){
                        left++;
                        continue;
                    }
                    else if(right+1<nums.length&& nums[right]==nums[right+1]){
                        right--;
                        continue;
                    }
                    else{
                        result.add(Arrays.asList(new Integer[]{curNum,nums[i],nums[left],nums[right]}));
                        left++;
                        right--;
                    }
                }
            }
        }
    }
}

课后总结

经过两数之和、三数之和、四数之和这些题目，三指针的基本玩法我们已经玩转了。以后看到类似的题目可以优先考虑使用三指针求解辣。