LeetCode_双指针_中等_18.四数之和

以你之姓@ 2023-10-06 18:04 19阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）
 *  4.扩展

## 1.题目 ##

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

**示例 1：**  
输入：nums = \[1,0,-1,0,-2,2\], target = 0  
输出：\[\[-2,-1,1,2\],\[-2,0,0,2\],\[-1,0,0,1\]\]

**示例 2：**  
输入：nums = \[\], target = 0  
输出：\[\]

**提示：**  
0 <= nums.length <= 200  
\-109 <= nums\[i\] <= 109  
\-109 <= target <= 109

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/4sum

## 2.思路 ##

（1）暴力穷举法  
其思想是使用四层for循环，穷举所有可能的情况，将符合题目条件的及结果保存到res中，值得注意的是在查找的过程中要去掉重复的四元组。此外，为了提高效率，可以进行一些剪枝操作。

（2）排序 & 双指针法  
此处的思路与[LeetCode\_双指针\_中等\_15.三数之和][LeetCode_15.]这题的思路 2 类似，只不过元素个数为4。具体思路就是穷举第一个元素 nums\[i\]，然后改写【15.三数之和】中思路 2 的代码来找出和为 target - nums\[i\] 的三元组，最后组合出和为 target 的四元组即可。

相关题目：  
[LeetCode\_双指针\_哈希表\_简单\_1.两数之和][LeetCode_1.]  
[LeetCode\_双指针\_中等\_15.三数之和][LeetCode_15.]  
[LeetCode\_双指针\_中等\_16.最接近的三数之和][LeetCode_16.]  
[LeetCode\_双指针\_中等\_167.两数之和 II - 输入有序数组][LeetCode_167._ II -]  
[LeetCode\_哈希表\_中等\_454.四数相加 II][LeetCode_454._ II]

## 3.代码实现（Java） ##

//思路1————暴力穷举法
    class Solution {
        
        public List<List<Integer>> fourSum(int[] nums, int target) {
        
            if (nums == null || nums.length < 4) return new ArrayList<>();
            //给数组进行排序
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            int length = nums.length;
            for (int i = 0; i < length - 3; i++) {
        
                //剪枝操作
                if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
                if (nums[i] + nums[length - 1] + nums[length - 2] + nums[length - 3] < target) continue;
                //去除重复的四元组
                if (i > 0 && nums[i] == nums[i - 1]) continue;
                for (int j = i + 1; j < nums.length - 2; j++) {
        
                    //剪枝操作
                    if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
                    if (nums[i] + nums[j] + nums[length - 1] + nums[length - 2] < target) continue;
                    //去掉重复的四元组
                    if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                    for (int k = j + 1; k < nums.length - 1; k++) {
        
                        //剪枝操作
                        if (nums[i] + nums[j] + nums[k] + nums[k + 1] > target) break;
                        if (nums[i] + nums[j] + nums[k] + nums[length - 1] < target) continue;
                        //去掉重复的四元组
                        if (k > j + 1 && nums[k] == nums[k - 1]) continue;
                        for (int h = k + 1; h < nums.length; h++) {
        
                            //剪枝操作
                            if (nums[i] + nums[j] + nums[k] + nums[h] > target) break;
                            if (nums[i] + nums[j] + nums[k] + nums[length - 1] < target) continue;
                            //去掉重复的四元组
                            if (h > k + 1 && nums[h] == nums[h - 1]) continue;
                            if (nums[i] + nums[j] + nums[k] + nums[h] == target) {
        
                                res.add(new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[k], nums[h])));
                            }
                        }
                    }
                }
            }
            return res;
        }
    }

//思路2————排序 & 双指针法
    class Solution {
        
        public List<List<Integer>> fourSum(int[] nums, int target) {
        
            //对数组进行排序
            Arrays.sort(nums);
            //res 用于存储结果
            List<List<Integer>> res = new ArrayList<>();
            int length = nums.length;
            //穷举第一个元素
            for (int i = 0; i < length; i++) {
        
                //计算和为 target - nums[i] 的三元组
                List<List<Integer>> triples = threeSumTarget(nums, i + 1, target - nums[i]);
                for (List<Integer> triple : triples) {
        
                    triple.add(nums[i]);
                    res.add(triple);
                }
                //跳过重复的元素
                while (i < length - 1 && nums[i] == nums[i + 1]) {
        
                    i++;
                }
            }
            return res;
        }
        
        //计算有序数组 nums[satrt...nums.length - 1] 中所有和为 target 的三元组
        public List<List<Integer>> threeSumTarget(int[] nums, int start, int target) {
        
            int length = nums.length;
            List<List<Integer>> res = new ArrayList<>();
            //遍历三元组的第一个数
            for (int i = start; i < length; i++) {
        
                //计算有序数组 nums[satrt...length] 中所有和为 target - nums[i] 的元素对
                List<List<Integer>> tumples = twoSumTarget(nums, i + 1, target - nums[i]);
                for (List<Integer> tumple : tumples) {
        
                    tumple.add(nums[i]);
                    res.add(tumple);
                }
                //跳过重复元素
                while (i < length - 1 && nums[i] == nums[i + 1]) {
        
                    i++;
                }
            }
            return res;
        }
        
        //计算有序数组 nums[satrt...nums.length - 1] 中所有和为 target 的二元组
        public List<List<Integer>> twoSumTarget(int[] nums, int start, int target) {
        
            // res 用于存储结果
            List<List<Integer>> res = new ArrayList<>();
            int left = start;
            int right = nums.length - 1;
            while (left < right) {
        
                int sum = nums[left] + nums[right];
                int leftVal = nums[left], rightVal = nums[right];
                if (sum == target) {
        
                    //将找到的元素对保存起来
                    res.add(new ArrayList<>(Arrays.asList(nums[left], nums[right])));
                    //跳过所有重复的元素
                    while (left < right && nums[left] == leftVal) left++;
                    while (left < right && nums[right] == rightVal) right--;
                } else if (sum < target) {
        
                    //增大 sum 的值，即将 left 向右移动
                    while (left < right && nums[left] == leftVal) left++;
                } else {
        
                    //减小 sum 的值，即将 right 向左移动
                    while (left < right && nums[right] == rightVal) right--;
                }
            }
            //数组 nums 中不存在和为 target 的两个数
            return res;
        }
    }

## 4.扩展 ##

**如果将求 4Sum 扩展到求 nSum**，那么按照之前的思路，就是先找到和为 target - nums\[i\] 的 n - 1 元组，那么该 n - 1 元组再加上 nums\[i\] 便是和为 target 的 n 元组，所以下面的代码给出了求 nSum 问题的函数。需要注意的是在调用该函数之前，数组 nums 必须是**升序的**或者是经过升序排序的。

class Solution {
        
        //返回数组 nums 中和为 target 的 n 元组
        public List<List<Integer>> nSum(int[] nums, int n, int target) {
        
            int start = 0;
            Arrays.sort(nums);
            return nSumTarget(nums, n, start, target);
        }
        
        //返回数组 nums[start...nums.length - 1] 中和为 target 的 n 元组
        public List<List<Integer>> nSumTarget(int[] nums, int n, int start, int target) {
        
            // res 用于保存结果
            List<List<Integer>> res = new ArrayList<>();
            int length = nums.length;
            if (n < 2 || length < n) {
        
                return res;
            }
            if (n == 2) {
        
                //直接使用双指针
                int left = start;
                int right = length - 1;
                while (left < right) {
        
                    int sum = nums[left] + nums[right];
                    int leftVal = nums[left], rightVal = nums[right];
                    if (sum == target) {
        
                        //将找到的元素对保存起来
                        res.add(new ArrayList<>(Arrays.asList(nums[left], nums[right])));
                        //跳过所有重复的元素
                        while (left < right && nums[left] == leftVal) {
        
                            left++;
                        }
                        while (left < right && nums[right] == rightVal) {
        
                            right--;
                        }
                    } else if (sum < target) {
        
                        //增大 sum 的值，即将 left 向右移动，同时跳过重复元素
                        while (left < right && nums[left] == leftVal) {
        
                            left++;
                        }
                    } else {
        
                        //减小 sum 的值，即将 right 向左移动，同时跳过重复元素
                        while (left < right && nums[right] == rightVal) {
        
                            right--;
                        }
                    }
                }
            } else {
        
                //当 n > 2 时，使用递归计算 (n - 1)SumTarget
                for (int i = start; i < length; i++) {
        
                    List<List<Integer>> sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                    //如果能找到和为 target - nums[i] 的 n - 1 元组，那么该 n - 1 元组再加上 nums[i] 便是和为 target 的 n 元组
                    for (List<Integer> arr : sub) {
        
                        arr.add(nums[i]);
                        res.add(arr);
                    }
                    //跳过重复的元素
                    while (i < length - 1 && nums[i] == nums[i + 1]) {
        
                        i++;
                    }
                }
            }
            return res;
        }
    }

[LeetCode_15.]: https://blog.csdn.net/weixin_43004044/article/details/118107655
[LeetCode_1.]: https://blog.csdn.net/weixin_43004044/article/details/118055101
[LeetCode_16.]: https://blog.csdn.net/weixin_43004044/article/details/118110152
[LeetCode_167._ II -]: https://blog.csdn.net/weixin_43004044/article/details/129296040
[LeetCode_454._ II]: https://blog.csdn.net/weixin_43004044/article/details/125439346