【每日一题】LeetCode - 三数之和

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != ji != kj != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

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

示例

示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:满足条件的三元组为 [-1, 0, 1][-1, -1, 2]

示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0

示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0

思路分析

这个问题的核心思路是找到数组中的三个数,其和为 0,同时要避免重复的组合。为了解决这个问题,我们可以通过排序和双指针的结合来有效地实现。

步骤:

  1. 排序数组:首先将 nums 数组按升序排序,便于后续使用双指针寻找满足条件的三元组。
  2. 遍历数组:固定一个数,然后使用双指针在剩余的部分查找满足条件的两个数。
  3. 避免重复
    • 如果当前固定的数和前一个数相同,可以直接跳过,以避免重复三元组。
    • 双指针过程中,若左右指针指向的数值和前一个数相同,同样跳过。

这个思路使得代码在处理每个三元组时,只计算不重复的组合。

实现代码

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ans;sort(nums.begin(), nums.end());  // 第一步:排序数组for(int a = 0; a < nums.size(); a++) {if(nums[a] > 0) break;  // 如果当前数大于0,跳出循环,因为后面的数都更大,不可能和为0if(a > 0 && nums[a] == nums[a - 1]) continue;  // 避免重复// 初始化双指针int left = a + 1, right = nums.size() - 1;while(left < right) {int sum = nums[a] + nums[left] + nums[right];if(sum == 0) {ans.push_back({nums[a], nums[left], nums[right]});// 移动指针避免重复while(left < right && nums[left] == nums[left + 1]) left++;while(left < right && nums[right] == nums[right - 1]) right--;left++;right--;} else if(sum < 0) {left++;} else {right--;}} }return ans;}
};

代码讲解

  1. 排序sort(nums.begin(), nums.end()); 这一步可以简化后续查找过程,因为排序后的数组让双指针查找更有效率。
  2. 外层循环:遍历数组 nums,每次固定一个数 nums[a]。当 nums[a] > 0 时,直接退出循环,因为在排序数组中,后续数值都更大,无法达到 0
  3. 双指针:对于每个固定数,用双指针在剩余部分查找两数之和为 -nums[a] 的组合。
    • 如果找到和为 0 的组合,将三元组加入结果集中。
    • 移动指针时检查是否有重复数,若有则跳过,以避免重复解。

时空复杂度分析

  • 时间复杂度O(n^2)
    • 外层循环复杂度为 O(n),双指针查找复杂度为 O(n),因此总体复杂度为 O(n^2)
  • 空间复杂度O(log(n))O(n),取决于排序算法的实现方式。返回结果不计入空间复杂度。

在这里插入图片描述

比较其他实现方式

一种直接的实现方式是三重循环,但这样会导致 O(n^3) 的时间复杂度,效率低下。而双指针配合排序的实现方法可以有效地减少时间复杂度到 O(n^2),在大数据量情况下具有显著的性能优势。

总结

通过排序和双指针结合,我们可以高效地解决三数之和问题。该方法不仅能避免重复,还能在 O(n^2) 的时间内找到所有符合条件的三元组,是一种简洁且高效的解法。

暴力破解实现

除了使用双指针的方法,我们还可以采用暴力破解的方法来解决这个问题。暴力破解的思路就是通过三重循环枚举所有可能的三元组,检查其和是否为零。虽然这种方法简单易懂,但效率较低。下面是暴力破解的实现代码:

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ans;for (int i = 0; i < nums.size(); i++) {for (int j = i + 1; j < nums.size(); j++) {for (int k = j + 1; k < nums.size(); k++) {if (nums[i] + nums[j] + nums[k] == 0) {vector<int> triplet = {nums[i], nums[j], nums[k]};// 检查三元组是否已存在于答案中if (find(ans.begin(), ans.end(), triplet) == ans.end()) {ans.push_back(triplet);}}}}}return ans;}
};

代码讲解

  1. 三重循环:外层循环遍历第一个数,内层循环遍历第二个和第三个数。
  2. 条件判断:检查三个数的和是否为零,如果满足条件则将三元组加入结果集中。
  3. 避免重复:在加入结果集之前,使用 find 函数检查该三元组是否已经存在。

时空复杂度分析

  • 时间复杂度O(n^3)
    • 三重循环的实现方式使得时间复杂度达到 O(n^3),当 n 较大时,效率非常低下。
  • 空间复杂度O(n),用于存储结果集,最坏情况下会保存所有三元组。

在这里插入图片描述

总结比较

暴力破解法虽然简单直观,但对于大规模数据,效率低下。而通过排序与双指针的方法,可以将时间复杂度降低至 O(n^2),适用于大数据场景。因此,在实际应用中,推荐使用双指针的方法解决三数之和问题。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/464174.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

基于 Canal + Elasticsearch 的业务操作日志解决方案

一、问题来源 在日常的业务系统中&#xff0c;操作日志是不可或缺的一部分。它能帮助我们追踪用户的操作行为&#xff0c;记录关键数据的变更&#xff0c;甚至在必要时支持操作回滚。最近&#xff0c;我们接到客户的需求&#xff0c;希望在系统中实现一个业务操作日志管理的功能…

Python并发编程库:Asyncio的异步编程实战

Python并发编程库&#xff1a;Asyncio的异步编程实战 在现代应用中&#xff0c;并发和高效的I/O处理是影响系统性能的关键因素之一。Python的asyncio库是专为异步编程设计的模块&#xff0c;提供了一种更加高效、易读的并发编程方式&#xff0c;适用于处理大量的I/O密集型任务…

【Vue项目1】第一篇

Vue项目1学习第一篇 01. 环境配置介绍和项目搭建02. Router路由配置引入03. ElementPlus引入和按需加载04. layout布局和菜单aside组件创建05. aside样式问题和treeMenu组件拆分06. treeMenu组件递归实现 01. 环境配置介绍和项目搭建 &#xff08;1&#xff09;安装node.js …

WPF使用Prism框架首页界面

1. 首先确保已经下载了NuGet包MaterialDesignThemes 2.我们通过包的项目URL可以跳转到Github上查看源码 3.找到首页所在的代码位置 4.将代码复制下来&#xff0c;删除掉自己不需要的东西&#xff0c;最终如下 <materialDesign:DialogHostDialogTheme"Inherit"Ide…

Golang | Leetcode Golang题解之第524题通过删除字母匹配到字典里最长单词

题目&#xff1a; 题解&#xff1a; func findLongestWord(s string, dictionary []string) (ans string) {m : len(s)f : make([][26]int, m1)for i : range f[m] {f[m][i] m}for i : m - 1; i > 0; i-- {f[i] f[i1]f[i][s[i]-a] i}outer:for _, t : range dictionary …

无人机的就业前景怎么样?

无人机的就业前景在当前及未来一段时间内都非常广阔。随着低空经济的蓬勃发展&#xff0c;无人机在农业、公安、测绘、交通、应急救援、影视拍摄等多个领域得到了广泛应用&#xff0c;对无人机操控员和相关专业人才的需求也随之急剧增加。 一、无人机操控员的就业前景 1. 高需…

如何将钉钉新收款单数据高效集成到MySQL

钉钉数据集成到MySQL的技术案例分享 在企业信息化管理中&#xff0c;数据的高效流动和处理至关重要。本文将分享一个具体的系统对接集成案例&#xff1a;如何将钉钉平台上的新收款单&#xff08;收款退款单&#xff09;数据集成到MySQL数据库中&#xff0c;方案名称为“dd-新收…

批量修改图片大小+删除空白页+手写签名

插入图片右键设置大小 设置对象格式 高度&#xff0c;宽度同一 最后一张图片拖到最后 alt键一下吸附好 ctrla全选图片 对齐 纵向分布 删除空白页 前面有文字 CTRL删除键 上一页是表格 CTRLd 勾选隐藏文字 手写签名 手机拍摄签名 发到电脑 文档里插入图…

软设师知识点-计算机网络

计算机网络 在一台安装好TCP/IP协议的计算机上&#xff0c;当网络连接不可用时&#xff0c;为了测试编写好的网络程序&#xff0c;通常使用的目的主机IP地址127.0.0.1&#xff08;本地回送地址&#xff09; *网络设备 物理层的互传设备&#xff1a;中继器(用于扩展局域网网段…

40.第二阶段x86游戏实战2-初识lua

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 本次游戏没法给 内容参考于&#xff1a;微尘网络安全 本人写的内容纯属胡编乱造&#xff0c;全都是合成造假&#xff0c;仅仅只是为了娱乐&#xff0c;请不要…

Docker可视化管理面板DPanel的安装

本文软件由网友 rui 推荐&#xff1b; 什么是 DPanel &#xff1f; DPanel 是一款 Docker 可视化管理面板&#xff0c;旨在简化 Docker 容器、镜像和文件的管理。它提供了一系列功能&#xff0c;使用户能够更轻松地管理和部署 Docker 环境。 软件特点&#xff1a; 可视化管理&…

Nature文章《deep learning》文章翻译

这篇文章是对Nature上《deep learning》文章的翻译。原作者 Yann LeCun, Yoshua Bengio& Geoffrey Hinton。 这篇文章的中心思想是深入探讨深度学习在机器学习中的革命性贡献&#xff0c;重点介绍其在特征学习、监督学习、无监督学习等方面的突破&#xff0c;并阐述其在图…

低代码用户中心:简化开发,提升效率的新时代

随着数字化转型的加速&#xff0c;企业对于快速交付高质量应用的需求日益增长。在这个背景下&#xff0c;低代码开发平台应运而生&#xff0c;成为越来越多企业和开发者的首选工具。今天&#xff0c;我们将聚焦于低代码用户中心&#xff0c;探讨其如何帮助开发者简化流程、提升…

leetcode71:简化路径

给你一个字符串 path &#xff0c;表示指向某一文件或目录的 Unix 风格 绝对路径 &#xff08;以 / 开头&#xff09;&#xff0c;请你将其转化为 更加简洁的规范路径。 在 Unix 风格的文件系统中规则如下&#xff1a; 一个点 . 表示当前目录本身。此外&#xff0c;两个点 ..…

2、liunx网络基础

一、TCP/IP协议概述 Linux服务器默认网卡配置文件在/etc/sysconfig/network-scripts/下&#xff0c;命名的名称一般为:ifcfg-eth0 ifcfg-eth1 &#xff0c;eth0表示第一块网卡&#xff0c;eth1表示第二块网卡&#xff0c;依次类推。一般DELL R720标配有4块千兆网卡。 TCP/IP&a…

[neo4j报错]py2neo.errors.ClientError: [Request.Invalid] Not Found解决方案

报错源代码 g Graph(http://localhost:7687, auth("neo4j", "password"))或许这是从网上复制下来的代码&#xff0c;看上去没什么问题&#xff0c;但实际上 要结合具体的浏览器上的地址来看&#xff0c;具体如下&#xff1a; 看到了吗&#xff0c;这里才…

WPF+MVVM案例实战(二十一)- 制作一个侧边弹窗栏(AB类)

文章目录 1、案例效果1、侧边栏分类2、AB类侧边弹窗实现1.文件创建2、样式代码与功能代码实现3、功能代码实现 3 运行效果4、源代码获取 1、案例效果 1、侧边栏分类 A类 &#xff1a;左侧弹出侧边栏B类 &#xff1a;右侧弹出侧边栏C类 &#xff1a;顶部弹出侧边栏D类 &#xf…

基于Multisim数控直流稳压电源电路(含仿真和报告)

【全套资料.zip】数控直流稳压电源电路设计Multisim仿真设计数字电子技术 文章目录 功能一、Multisim仿真源文件二、原理文档报告资料下载【Multisim仿真报告讲解视频.zip】 功能 1.输出直流电压调节范围5-12V。 2.输出电流0-500mA。 3.输出直流电压能步进调节&#xff0c;步…

原来大佬的测试用例都是这样写的...

1、测试点与测试用例 测试点不等于测试用例&#xff0c;这是我们首先需要认识到的。 问题1&#xff1a;这些测试点在内容上有重复&#xff0c;存在冗余。 问题2&#xff1a;一些测试点的测试输入不明确&#xff0c;不知道测试时要测试哪些。 问题3&#xff1a;总是在搭相似…