Leetcode算法Java全解答--015. 三数之和

灰太狼 2022-04-18 06:47 124阅读 0赞

# Leetcode算法Java全解答–015. 三数之和 #

### 文章目录 ###

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

## 题目 ##

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？

找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
    满足要求的三元组集合为：
    [
        [-1, 0, 1],
        [-1, -1, 2]
    ]

## 想法 ##

1.  暴力破解：

*  嵌套三层循环
    
     *  注意：遍历结果是否相同
     *  时间复杂度比较高

1.  先排序，以0位分割点，再进行计算

*  找到负数最大位置、正数最小位置、0的个数
    
     *  0超过三个，则肯定有个答案是000
     *  当没有负数或者没有正数的时候，直接返回
 *  滑动列表的方法
    
     *  以负数们为循环（最大值为数最大位置）
        
         *  负数的绝对值为目标
         *  双指针 left为下一个数，right为最大长度
         *  两数相加小于目标，则right左移，否则left右移
         *  通过nums\[leftIndex\] == nums\[leftIndex + 1\] 控制重复数据
            
             *  注意这里数组越界，要加个left<right判断

## 结果 ##

超过99%的测试案例

时间复杂度：复杂度最高的应该就是排序算法了Arrays.sort(nums)

空间复杂度：接收结果List<List> result

## 总结 ##

1.  想到了排序
2.  没有想到使用滑动列表
3.  在书写代码的时候，很多细节没有考虑到，比如重复

## 代码 ##

### 我的答案 ###

/*
     * Copyright (C), 2015-2018
     * FileName: Solution015
     * Author:   zhao
     * Date:     2018/11/9 19:45
     * Description: 15. 三数之和
     * History:
     * <author>          <time>          <version>          <desc>
     * 作者姓名           修改时间           版本号              描述
     */
    package com.lizhaoblog.mid;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.List;
    
    /**
     * 〈一句话功能简述〉<br>
     * 〈15. 三数之和〉
     *
     * @author zhao
     * @date 2018/11/9 19:45
     * @since 1.0.1
     */
    public class Solution015 {
    
        /**************************************
         * 题目
         给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
         找出所有满足条件且不重复的三元组。
    
         注意：答案中不可以包含重复的三元组。
    
         例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
         满足要求的三元组集合为：
         [
         [-1, 0, 1],
         [-1, -1, 2]
         ]
         **************************************/
    
        /**************************************
         *
         * 想法：
         *      1.暴力破解：
         *          嵌套三层循环
         *              注意：遍历结果是否相同
         *              时间复杂度比较高
         *      2.先排序，以0位分割点，再进行计算
         *          找到负数最大位置、正数最小位置、0的个数
         *              0超过三个，则肯定有个答案是000
         *              当没有负数或者没有正数的时候，直接返回
         *          滑动列表的方法
         *              以负数们为循环（最大值为数最大位置）
         *                  负数的绝对值为目标
         *                  双指针 left为下一个数，right为最大长度
         *                  两数相加小于目标，则right左移，否则left右移
         *                  通过nums[leftIndex] == nums[leftIndex + 1] 控制重复数据
         *                      注意这里数组越界，要价格left<right判断
         * 我的做法
         *      超过99%的测试案例
         *      时间复杂度：复杂度最高的应该就是排序算法了Arrays.sort(nums)
         *      空间复杂度：接收结果List<List<Integer>> result
         * 代码执行过程：
         *          找到负数最大位置、正数最小位置、0的个数
         *              0超过三个，则肯定有个答案是000
         *              当没有负数或者没有正数的时候，直接返回
         *          滑动列表的方法
         *              以负数们为循环（最大值为数最大位置）
         *                  负数的绝对值为目标
         *                  双指针 left为下一个数，right为最大长度
         *                  两数相加小于目标，则right左移，否则left右移
         *                  通过nums[leftIndex] == nums[leftIndex + 1] 控制重复数据
         *                      注意这里数组越界，要价格left<right判断
         * 总结：
         *      1. 想到了排序
         *      2. 没有想到使用滑动列表
         *      3. 在书写代码的时候，很多细节没有考虑到，比如重复
         * ***********************************/
        public List<List<Integer>> threeSum(int[] nums) {
            if (nums == null || nums.length < 1) {
                return Collections.EMPTY_LIST;
            }
    
            Arrays.sort(nums);
            int target = 0;
            int targetCount = 0;
            // 负数最大索引
            int spilt0 = -1;
            // 正数最小索引
            int spilt2 = -1;
    
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] < target) {
                    spilt0 = i;
                } else if (nums[i] == target) {
                    targetCount++;
                } else if (nums[i] > target) {
                    spilt2 = i;
                    break;
                }
            }
    
            // 出现超过三个0，就肯定有一个答案是000
            List<List<Integer>> result = new ArrayList<>();
            if (targetCount >= 3) {
                List<Integer> list = new ArrayList<>();
                list.add(0);
                list.add(0);
                list.add(0);
                result.add(list);
            }
    
            // 这种时候只有非负数，或者只有非正数，除了000，否则是凑不齐的
            if (spilt0 == -1 || spilt2 == -1) {
                // 这里有可能全部都是0,不然就肯定无法满足条件
                return result;
            }
    
            // 当整体数据有正有负，就遍历负数就好
            // 然后使用滑动列表
            // 以负数的绝对值为目标，后面2数相加小于目标，则左移，否则右移
            for (int i = 0; i <= spilt0; i++) {
                // 如果和之前那个数据相同，则会是重复事件
                if (i > 0 && nums[i] == nums[i - 1]) {
                    continue;
                }
    
                int val = nums[i] * -1;
                int leftIndex = i + 1;
                int rightIndex = nums.length - 1;
                while (leftIndex < rightIndex) {
                    int tmpVal = nums[leftIndex] + nums[rightIndex];
                    if (tmpVal > val) {
                        rightIndex--;
                    } else if (tmpVal < val) {
                        leftIndex++;
                    } else {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        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) {
            if (nums.length < 3) {
                return Collections.emptyList();
            }
            List<List<Integer>> res = new ArrayList<>();
            int minValue = Integer.MAX_VALUE;
            int maxValue = Integer.MIN_VALUE;
            int negSize = 0;
            int posSize = 0;
            int zeroSize = 0;
            for (int v : nums) {
                if (v < minValue) {
                    minValue = v;
                }
                if (v > maxValue) {
                    maxValue = v;
                }
                if (v > 0) {
                    posSize++;
                } else if (v < 0) {
                    negSize++;
                } else {
                    zeroSize++;
                }
            }
            if (zeroSize >= 3) {
                res.add(Arrays.asList(0, 0, 0));
            }
            if (negSize == 0 || posSize == 0) {
                return res;
            }
            if (minValue * 2 + maxValue > 0) {
                maxValue = -minValue * 2;
            } else if (maxValue * 2 + minValue < 0) {
                minValue = -maxValue * 2;
            }
    
            int[] map = new int[maxValue - minValue + 1];
            int[] negs = new int[negSize];
            int[] poses = new int[posSize];
            negSize = 0;
            posSize = 0;
            for (int v : nums) {
                if (v >= minValue && v <= maxValue) {
                    if (map[v - minValue]++ == 0) {
                        if (v > 0) {
                            poses[posSize++] = v;
                        } else if (v < 0) {
                            negs[negSize++] = v;
                        }
                    }
                }
            }
            Arrays.sort(poses, 0, posSize);
            Arrays.sort(negs, 0, negSize);
            int basej = 0;
            for (int i = negSize - 1; i >= 0; i--) {
                int nv = negs[i];
                int minp = (-nv) >>> 1;
                while (basej < posSize && poses[basej] < minp) {
                    basej++;
                }
                for (int j = basej; j < posSize; j++) {
                    int pv = poses[j];
                    int cv = 0 - nv - pv;
                    if (cv >= nv && cv <= pv) {
                        if (cv == nv) {
                            if (map[nv - minValue] > 1) {
                                res.add(Arrays.asList(nv, nv, pv));
                            }
                        } else if (cv == pv) {
                            if (map[pv - minValue] > 1) {
                                res.add(Arrays.asList(nv, pv, pv));
                            }
                        } else {
                            if (map[cv - minValue] > 0) {
                                res.add(Arrays.asList(nv, cv, pv));
                            }
                        }
                    } else if (cv < nv) {
                        break;
                    }
                }
            }
            return res;
        }

### 测试用例 ###

@Test
        public void test015() {
            // 创建测试案例
            int[] arr1 = new int[] { -1, 0, 1, 2, -1, -4 };
    
            // 测试案例期望值
            List<List<Integer>> expResult1 = new ArrayList<>();
            List<Integer> list1 = new ArrayList<>();
            list1.add(-1);
            list1.add(0);
            list1.add(1);
            List<Integer> list2 = new ArrayList<>();
            list2.add(-1);
            list2.add(-1);
            list2.add(2);
            expResult1.add(list1);
            expResult1.add(list2);
    
    
            // 执行方法
            Solution015 solution015 = new Solution015();
            List<List<Integer>> result1 = solution015.threeSum(arr1);
    
            // 判断期望值与实际值
            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

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