代码随想录算法训练营第十二天|第18题. 四数之和

文档讲解：代码随想录

难度：有一点点难度

附：寒假继续开始刷题更新刷题记录

passion！！！passion！！！passion！！！

第18题. 四数之和

力扣题目链接(opens new window)

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

注意：

答案中不可以包含重复的四元组。

示例：给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。满足要求的四元组集合为： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]

思路

可以将问题简单化：往期刷过两数之和和三数之和，所以可以尝试将四数之和转换为三数之和，三数之和的解题的一个巧妙思路如下：

为了降低时间复杂程度，可以对一些可以直接排除的元素进行去除：三数之和中如果一个数字大于目标数字，则可以直接去除（由于已知目标是0，故第一个数字不可以大于目标数字）

详细参考以下文档：

代码随想录

第15题. 三数之和

也可以参考本人往期作品中的“三数之和”

代码随想录算法训练营第十一天|383. 赎金信， 15. 三数之和

由于题目并没有表明该数组是有序k数组，故应先对数组进行排序（sort方法）；
进入循环1.1（k）
同理，对一些元素直接排除：因为目标的大小正负未知，故应该加一些条件：如果一个数字大于目标，但为了避免出现特殊情况（如num[k]=-4,目标是-10，）应该对该数字和目标进行正负分析并添加验证条件，可以判断 目标数字或num[k]的正负， 最后为代码实现为nums[i] > target && (nums[i] >=0 || target >= 0)
去除相同的数字（题目要求），因为已经进行了排序，故判断该数字的前（后）即可
进入循环2.1（i）（2代表为内层，.1代表是内层第一次循环，以下同理）
进行第二次进入步骤2，3（可以理解为将前两个数字和并为一个整体后，再进行一次判断）
设置左右指针，左指针为i的下一个元素，右指针为num数组的最后一个元素
进入循环3.1（判断条件为右指针应该大于左指针）
求四数之和：sum=num[k]+num[i]+num[left]+num[right],如果sum偏大则将右指针左移动（排序后，右侧数大于左侧），如果sum偏小则将左指针右移动，如果符合则将num[k]，num[i]，num[left]，num[right]计入result数组
进入循环4.1，4.2再次进行步骤4进行去重
左右指针都向中移动
所有循环结束返回result数组
定义测试部分：

补充

　在Java中，foreach循环也被称为增强型for循环。它可以用来遍历数组、集合或其他类似结构的数据。foreach循环的语法如下：

　　for (element_type element : collection) {

　　// 循环体

　　}

　　其中，element_type是集合中元素的类型，element是集合中每个元素的变量名，collection是需要遍历的集合。在循环体中，可以使用element变量来访问当前元素的值。

　　下面是一个示例，展示了如何使用foreach循环来遍历一个整型数组：

　　int[] numbers = {1, 2, 3, 4, 5};

　　for (int number : numbers) {

　　System.out.println(number);

　　}

　　在这个示例中，我们定义了一个整型数组numbers，然后使用foreach循环来遍历这个数组，并在循环体中打印出每个元素的值。输出结果如下：

　　除了数组，foreach循环还可以用于遍历其他类型的集合，例如List、Set、Map等。不过需要注意的是，对于Map类型的集合，foreach循环只能遍历其中的键或值，而不能同时访问键和值。

代码如下：

import java.util.*;

public class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);  // 排序数组
        List<List<Integer>> result = new ArrayList<>();  // 放结果
        for (int k = 0; k < nums.length; k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
                break;
            }
            // 去除nums[k]相同的元素
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.length; i++) {
                // 第二级剪枝
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;
                }
                // 去除nums[i]相同的元素
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.length - 1;
                while (right > left) {
                    long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1, 0, -1, 0, -2, 2};
        int target = 0;
        List<List<Integer>> results = solution.fourSum(nums, target);
        for (List<Integer> result : results) {
            System.out.println(result);
        }
    }
}