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

Posted by lizhao on 07-09,2019

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://blog.csdn.net/cmqwan

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

如有疑问请联系,联系方式:QQ3060507060