Leetcode算法Java全解答--18. 四数之和

╰半橙微兮° 2022-04-15 03:21 138阅读 0赞

# Leetcode算法Java全解答–18. 四数之和 #

### 文章目录 ###

*  Leetcode算法Java全解答--18. 四数之和
 *   *  题目
     *  想法
     *  结果
     *  总结
     *  代码
     *   *  我的答案
         *  大佬们的答案
         *  测试用例
     *  其他

## 题目 ##

给定一个包含 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]
    ]

## 想法 ##

1.  暴力破解：四层循环 一把梭
2.  套用三层循环的思维

原来三数之和 循环一次加滑动列表 改成 循环两次加滑动列表

复杂度：n3/n

详细可以看这个三数之和：  
[Leetcode算法Java全解答–015. 三数之和][Leetcode_Java_015.]

## 结果 ##

超过91%的测试案例

时间复杂度/空间复杂度：n3/n

## 总结 ##

之前卡在这题没有去做，就是自己没有想着动手写

## 代码 ##

### 我的答案 ###

/**************************************
     * 题目
     给定一个包含 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]
     ]
     **************************************/
    
    /**************************************
     *
     * 想法：
     *      1. 暴力破解：四层循环 一把梭
     *      2. 套用三层循环的思维
     *          原来 循环一次加滑动列表 改成 循环两次加滑动列表
     *          详细可以看这个：
     *          复杂度：n3/n
     *
     * 我的做法
     *      超过91%的测试案例
     *      时间复杂度/空间复杂度：n3/n
     * 代码执行过程：
     *
     * 总结：
     *      1. 之前卡在这题没有去做，就是自己没有想着动手写
     * ***********************************/
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if (nums == null || nums.length < 4) {
            return Collections.EMPTY_LIST;
        }
        Arrays.sort(nums);
    
        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < nums.length - 3; i++) {
    
            // 如果和之前那个数据相同，则会是重复事件
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int valI = nums[i];
    
            for (int j = i + 1; j < nums.length - 2; j++) {
    
                // 如果和之前那个数据相同，则会是重复事件
                if (j - i > 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
    
                int valJ = nums[j];
    
                int leftIndex = j + 1;
                int rightIndex = nums.length - 1;
    
                while (leftIndex < rightIndex) {
                    int tmpVal = nums[leftIndex] + nums[rightIndex] + valI + valJ;
    
                    if (tmpVal > target) {
                        rightIndex--;
                    } else if (tmpVal < target) {
                        leftIndex++;
                    } else {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[leftIndex]);
                        list.add(nums[rightIndex]);
                        result.add(list);
                        // 用nums[leftIndex] == nums[leftIndex + 1]控制重复
                        while (leftIndex < rightIndex && nums[leftIndex] == nums[leftIndex + 1]) {
                            leftIndex++;
                        }
                        while (leftIndex < rightIndex && nums[rightIndex] == nums[rightIndex - 1]) {
                            rightIndex--;
                        }
                        leftIndex++;
                        rightIndex--;
                    }
                }
            }
        }
        return result;
    }

### 大佬们的答案 ###

/**************************************
     * 比我好的答案 better
     * ***********************************/
    public List<List<Integer>> better(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        int len = nums.length;
        if (nums == null || len < 4) {
            return result;
        }
        //排序
        Arrays.sort(nums);
        //确定两个值两层循环然后确定左右指针
        //外循环
        for (int i = 0; i < len - 3; i++) {
            //判断相等
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            //最小值大于目标值结束
            if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
                break;
            }
            //最大值小于目标值跳过此循环
            if (nums[i] + nums[len - 1] + nums[len - 2] + nums[len - 3] < target) {
                continue;
            }
            //内循环
            for (int j = i + 1; j < len - 2; j++) {
                //判断相等
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                //最小值大于目标值结束
                if (nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) {
                    break;
                }
                //最大值小于目标值跳过此循环
                if (nums[i] + nums[j] + nums[len - 2] + nums[len - 1] < target) {
                    continue;
                }
                //左右指针寻找满足条件的值
                int left = j + 1;
                int right = len - 1;
                while (left < right) {
                    int sum = nums[left] + nums[right] + nums[i] + nums[j];
                    if (sum == target) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left - 1]) {
                            left++;
                        }
                        while (left < right && nums[right] == nums[right + 1]) {
                            right--;
                        }
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
    
                }
            }
        }
        return result;
    }

### 测试用例 ###

@Test
    public void test018() {
        // 创建测试案例
        //        int[] arr1 = new int[] { 1, 0, -1, 0, -2, 2 };
        int[] arr1 = new int[] { 0, 0, 0, 0 };
        int target1 = 0;
    
        // 测试案例期望值
        List<List<Integer>> expResult1 = new ArrayList<>();
    
        List<Integer> list1 = new ArrayList<>();
        list1.add(-1);
        list1.add(0);
        list1.add(0);
        list1.add(1);
        List<Integer> list2 = new ArrayList<>();
        list2.add(-2);
        list2.add(-1);
        list2.add(1);
        list2.add(2);
        List<Integer> list3 = new ArrayList<>();
        list2.add(-2);
        list2.add(0);
        list2.add(0);
        list2.add(2);
        expResult1.add(list1);
        expResult1.add(list2);
        expResult1.add(list3);
    
        // 执行方法
        Solution018 solution018 = new Solution018();
        List<List<Integer>> result1 = solution018.fourSum(arr1, target1);
    
        // 判断期望值与实际值
        Assert.assertEquals(expResult1, result1);
    
    }

## 其他 ##

代码托管码云地址：[https://gitee.com/lizhaoandroid/LeetCodeAll.git][https_gitee.com_lizhaoandroid_LeetCodeAll.git]

查看其他内容可以点击专栏或者我的博客哈：[https://blog.csdn.net/cmqwan][https_blog.csdn.net_cmqwan]

“大佬们的答案” 标签来自leetcode，侵权请联系我进行删改

如有疑问请联系，联系方式：QQ3060507060

[Leetcode_Java_015.]: https://blog.csdn.net/cmqwan/article/details/83903491
[https_gitee.com_lizhaoandroid_LeetCodeAll.git]: https://gitee.com/lizhaoandroid/LeetCodeAll.git
[https_blog.csdn.net_cmqwan]: https://blog.csdn.net/cmqwan