18. 四数之和（算法思维系列）

一时失言乱红尘 2023-10-05 20:28 27阅读 0赞

#### 18. 四数之和 ####

*  题目
 *  解题思路
 *  代码

## 题目 ##

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]

## 解题思路 ##

直接套用nSum模板即可，详情见书325

## 代码 ##

class Solution {
        
        public List<List<Integer>> fourSum(int[] nums, int target) {
        
            Arrays.sort(nums);
            return nSumTarget(nums,target,4,0);
        }
    
    
         /**
         * 计算数组中所有和为target的n元组
         * 注意：必须先给数组排序才可以使用本模板
         *
         * @param nums   数组
         * @param target 目标
         * @param n      几元组，也就是几sum问题
         * @param start  从nums[start]开始，计算有序数组中所有和为target的n元组
         * @return
         */
        public List<List<Integer>> nSumTarget(int[] nums, int target, int n, int start) {
        
            int size = nums.length;
            List<List<Integer>> res = new ArrayList<>();
    
            //至少要2Sum才能调用这个框架
            if (n < 2 || size < n) {
        
                return res;
            }
    
            if (n == 2) {
        //那就用2Sum标准的双指针那一套解法
                int lo = start;
                int hi = size - 1;
    
                while (lo < hi) {
        
                    int sum = nums[lo] + nums[hi];
                    int left = nums[lo];
                    int right = nums[hi];
    
                    if (sum < target) {
        
                        lo++;
                    } else if (sum > target) {
        
                        hi--;
                    } else {
        
                        //将满足条件的值添加到res
                        List<Integer> listM = new ArrayList<Integer>();
                        listM.add(left);
                        listM.add(right);
                        res.add(listM);
    //题目要求的是不重复的答案，如何排除重复呢？nums[lo]==left代表出现了重复元素，那么lo还要前进，直到不是重复元素为止。
                        while (lo < hi && nums[lo] == left) {
        
                            lo++;
                        }
                        while (lo < hi && nums[hi] == right) {
        
                            hi--;
                        }
                    }
                }
            } else {
        //不止2Sum的规模
    
                for (int i = start; i < size; i++) {
        
                    //对于target-num[i]，再进行(n-1)Sum运算
                    List<List<Integer>> subs = nSumTarget(nums, target - nums[i], n - 1, i + 1);
                    
                    for (List<Integer> sub : subs) {
        
                        //(n-1)Sum + nums[i]就是nSum
                        sub.add(nums[i]);
                        res.add(sub);
                    }
                    //跳过重复元素
                    while (i < size - 1 && nums[i] == nums[i + 1]) i++;
    
                }
            }
    
    
            return res;
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210226001251190.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70