萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣第15题-三数之和

发表于 2022-03-29 | 分类于 力扣刷题 | 0 | 阅读次数 22

题目描述

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。

样例

示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例 2:
输入:nums = []
输出:[]

示例 3:
输入:nums = [0]
输出:[]

题目评估

知识点:数组、双指针、排序
官方难度:中等

分析

一搭眼的方法就是三重循环暴力,但是会有重复。排序后可以方便跳过重复。
nums[a] + nums[b] + nums[c] = 0,当 nums[a] 不变的时候,nums[b] 越大,nums[c] 必须越小才能使等式继续有可能等于 0,所以当 a 指针固定时 b 指针向右移的情况下 c 指针指向的数字必须越来越小。故当 a 指针不动,时 b 和 c 组成双指针,从 a + 1 到 nums.length - 1 之间向中间移动,当 b 和 c 指针重合便可以开始下一轮第一重循环。

Java代码题解

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        // 排序
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            // 第一个数字去重
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1, k = nums.length - 1; j < nums.length; j++) {
                // 第二个数去重
                if (j > i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                // 保证第二个指针在第三个指针左边的情况下,结果不符就左移第三指针使第三个数字变小
                while (j < k && nums[i] + nums[j] + nums[k] > 0) {
                    k--;
                }
                // 指针重合跳出
                if (j >= k) {
                    break;
                }
                // 如果相加等于0放入结果集
                if (nums[i] + nums[j] + nums[k] == 0) {
                    List<Integer> current = new ArrayList<>();
                    current.add(nums[i]);
                    current.add(nums[j]);
                    current.add(nums[k]);
                    res.add(current);
                }
            }
        }
        return res;
    }
}

复杂度分析

时间复杂度:O(N^2),其中 N 是数组 nums 的长度。
空间复杂度:O(logN)。我们忽略存储答案的空间,额外的排序的空间复杂度为 O(logN)。然而我们修改了输入的数组 nums,在实际情况下不一定允许,因此也可以看成使用了一个额外的数组存储了 nums 的副本并进行排序,空间复杂度为 O(N)。

# 算法 # 程序设计 # 力扣
力扣14题-最长公共前缀
力扣第16题-最接近的三数之和
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

67 日志
17 分类
41 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2022 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持