萤火小屋

优律的知识库

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

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

力扣第15题-三数之和

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

题目描述

给你一个包含 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题-最接近的三数之和
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

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