当前位置：首页 > article >正文

代码随想录刷题day21|（哈希表篇）18.四数之和

article 2025/2/2 14:12:21

一、哈希表理论基础

二、题目思路及难点

三、相关算法题目

四、总结

三数之和和四数之和的不同

一、哈希表理论基础

详见代码随想录刷题day15|（哈希表篇）242.有效的字母异位词、383.赎金信-CSDN博客

二、题目思路及难点

思路：类比三数之和，只是多加一层for循环，多进行一次剪枝和去重操作，同时内层三数之和的for循环中，对 i 的剪枝和去重操作也略有不同；

PS：剪枝是指如果此时a（nums[i]）已经＞0，那么三数之和不可能再＞0，所以返回结果；

for(int i = 0;i < nums.length;i++){

if(nums[i] > 0){

//数组全为正数三数之和不可能为0

return result;

}//剪枝

首先外层循环for，定义变量 k 代表a，内层for循环 i 代表b，left和right分别代表c、d，并初始化为i+1、nums.length-1；那么sum=a + b + c + d=nums[k] + nums[i] + nums[left] + nums[right]；

先对k(a)进行剪枝和去重，之后进入内层for，对 i(b) 进行剪枝和去重，然后初始化left、right，进入while，先判断sum和target（逻辑同三数之和），进行left、right的移动，得到一次结果后，再对c、d去重，最后更新left和right的值，这里思路同三数之和；

对a去重时，判断:nums[k] == nums[k-1]，同时保证 k > 0；

对b去重时，判断:nums[i] == nums[i-1]，同时保证 i > k+1；

对c和d去重，分别判断：nums[left] == nums[left + 1]、nums[right] == nums[right - 1]，如果相等，那么分别进行left++，right--；

难点

Q：一级剪枝和去重操作（对 k/a）？

A：剪枝：if(nums[k] > target && nums[k] >= 0)

target可以是正数也可以是负数，比如 -4 -1 0 0，target = -5，k=0，numks[k]=-4 > -5，如果此时break 出错，[-4,-1,0,0]是符合条件的四元组，所以只判断nums[k] > target 不全面，应当同时满足 nums[k] >= 0 保证数组中元素均为非负数；

去重：if(k > 0 && nums[k] == nums[k-1])

思路同三数之和；

Q：二级剪枝和去重操作（对 i/b）？

A：剪枝：if(nums[i] + nums[k] > target && nums[k] + nums[i] >= 0)

此时，将nums[i] + nums[k]看做整体，逻辑同一级剪枝；

去重： if(i > k + 1 && nums[i] == nums[i-1])

注意 i 的取值判断和三数之和里不同；

Q：去重和剪枝的区别？返回代码？

A：剪枝中是 break，去重中是continue；

剪枝：

对于一级循环中 k来说，如果nums[k] ＞ target 且 nums[k] ≥ 0，数组升序，则说明整个数组都没有符合条件的四元组，所以可以退出循环，返回结果，故为berak，此外一级循环中，break等价于return result;

对于二级循环 i 来说，如果a+b＞ target，且a+b≥0，则说明，没有一对c+d使得a+b+c+d=target，所以break退出循环，这里指的是二级循环，所以 return result ≠ break，前者是结束程序，返回结果，后者只是退出二层循环for(i)，但会接着执行外层循环for(k)；

去重：

只是有重复数据，那么continue跳出本次循环，更新i/k 直到没有重复数据即可；

Q：去重和剪枝操作是if还是while？

A：都是if；

如果是while循环，i/k值不会更新，没有条件控制语句，只有跳出本次循环，i/k值才会更新，所以不能用while，用if判断，进入下次循环后，仍会进行剪枝和去重的操作；

Q：更新left、right 和对left、right去重的先后顺序？

A：先去重后更新；

比如 7 7 7，while去重后，left/right会更新到最后一个相同的元素处，即上面最后一个7，然后更新，left/right+1，就会从下一个不为7的元素开始判断；

如果先更新后去重，比如 -1 -1 0 1 2 2

left先指向第一个-1，更新后，指向第二个-1，去重条件不满足（-1 ≠ 0，但是此时left是和第一个-1相等的）从当前位置判断sum，如果right也有相同情况，则出现重复四元组，无法达到去重效果；

三、相关算法题目

18.四数之和

18. 四数之和 - 力扣（LeetCode）

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<List<Integer>> ();
        //对数组排序 a+b+c+d=target
        Arrays.sort(nums);
        //一级剪枝和去重
        for(int k = 0;k < nums.length;k++){
            //对a剪枝
            if(nums[k] > target && nums[k] >= 0){
                return result;
                //break;
            }
            //对a去重
            if(k > 0 && nums[k] == nums[k-1]){
                continue;
            }
            //二级剪枝和去重
            for(int i = k + 1;i < nums.length;i++){
                //对b剪枝
                if(nums[i] + nums[k] > target && nums[k] + nums[i] >= 0){
                    break;
                    //return result;
                }
                //对b去重
                if(i > k + 1 && nums[i] == nums[i-1]){
                    continue;
                }
                //判断sum 移动left和right
                int left = i + 1;
                int right = nums.length - 1;
                while(left < right){
                    int sum = nums[k] + nums[i] + nums[left] + nums[right];
                    if(sum < target){
                        left++;
                    }else if(sum > target){
                        right--;
                    }else{
                        result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        //对left、right去重
                        while(left < right && nums[left] == nums[left + 1]){
                            left++;
                        }
                        while(left < right && nums[right] == nums[right - 1]){
                            right--;
                        }
                        //更新left、right
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}