15.三数之和

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

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

示例 1:

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。

示例 2:

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

示例 3:

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

提示:

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

这题也是双指针的应用。

要求三元组不能重复,可以想到排个序再遍历。很容易想到三层遍历解法,但是时间复杂度太高了,采用双指针可以降低时间复杂度。第一层遍历元素指针记为i,开始第二层遍历之前要判重,跳过重复的元素。在第二层遍历里使用双指针:l从左往右遍历,r从右往左遍历(l和r的和是固定的,l要增大,r就要减小,所以是相向的),判断满满足条件的,push_back三元组。

复杂度分析

·时间复杂度:O(N^{^{2}}),其中 N 是数组 nums 的长度。

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

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());vector<vector<int>> a;for (int i = 0; i < nums.size(); i++) {if (i > 0 && nums[i] == nums[i - 1]) {continue;}int r = nums.size() - 1;int t = -nums[i];for (int l = i + 1; l < nums.size(); l++) {if (l> i + 1 && nums[l] == nums[l - 1]) {continue;}while (l < r && nums[l] + nums[r] > t) {r--;}if (l == r) {break;}if (nums[l] + nums[r] == t) {a.push_back({nums[i], nums[l], nums[r]});}}}return a;}
};

看到更好理解的一个版本:

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(), nums.end());int l = 0, r = nums.size() - 1;vector<vector<int> > ans;for (int i = 0; i < nums.size() - 2; ++i) {if (i > 0 && nums[i] == nums[i - 1]) continue; // 跳过重复的元素int l = i + 1, r = nums.size() - 1;while (l < r) {int sum = nums[i] + nums[l] + nums[r];if (sum == 0) {ans.push_back({nums[i], nums[l], nums[r]});while (l < r && nums[l] == nums[l + 1]) ++l; // 跳过重复的元素while (l < r && nums[r] == nums[r - 1]) --r; // 跳过重复的元素++l; --r;} else if (sum < 0) {++l;} else {--r;}}}return ans;}
};

 

 

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

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

相关文章

03_Webpack模块打包工具

03_Webpack模块打包工具 目录 知识点自测 以下哪个选项是 ECMAScript 默认导出和导入的语法&#xff1f; A&#xff1a;export 和 require B&#xff1a;module.exports {} 和 import 变量名 C&#xff1a;export default 和 import 变量名 D&#xff1a;export 和 import {…

实验七 用 MATLAB 设计 FIR 数字滤波器

实验目的 加深对窗函数法设计 FIR 数字滤波器的基本原理的理解。 学习用 Matlab 语言的窗函数法编写设计 FIR 数字滤波器的程序。 了解 Matlab 语言有关窗函数法设计 FIR 数字滤波器的常用函数用法。 掌握 FIR 滤波器的快速卷积实现原理。 不同滤波器的设计方法具有不同的优…

day07 接口测试(2)

目录 1、接口用例设计 1.1 接口测试的测试点 1.1.1 功能测试 &#xff01;&#xff01; &#xff08;1&#xff09;单接口功能&#xff1a; &#xff08;见1.3&#xff09; &#xff08;2&#xff09;业务场景功能:&#xff08;见1.4&#xff09; 1.1.2 性能测试&#xf…

CentOS 二进制安装部署MongoDB 4.0

一、安装MongoDB 1. 下载 MongoDB 二进制文件 前往 MongoDB 官方下载页面(https://www.mongodb.com/try/download/community) 选择对应版本的 tar 包。 wget https://fastdl.mongodb.org/linux/mongodb-linux-x86_64-4.0.28.tgz 2. 解压并移动至目标目录 解压文件&#xff…

《Scientific Reports》2024最新投稿经验

"Scientific Reports" 是Nature Portfolio旗下一本备受推崇的开放获取多学科期刊&#xff0c;自2011年起被JCR收录。这本月刊致力于发表自然科学、心理学、医学和工程学领域的突破性原创研究。它的收稿范围广泛&#xff0c;覆盖物理学、化学、生物学、地球科学、环境…

C++内存布局以及常用关键字

C内存布局以及常用关键字 C的内存空间 代码存储区域&#xff1a;常量区、代码区、静态区&#xff08;全局区&#xff09;、堆区、栈区 栈区向下增长&#xff0c;堆区向上增长。栈由系统管理&#xff0c;没有内存碎片&#xff0c;每个元素之间都是连续的&#xff0c;大小比较…

设计模式:19、桥接模式

目录 0、定义 1、桥接模式的四种角色 2、桥接模式的UML类图 3、示例代码 0、定义 将抽象部门与实现部分分离&#xff0c;使它们都可以独立地变化。 1、桥接模式的四种角色 抽象&#xff08;Abstraction&#xff09;&#xff1a;一个抽象类&#xff0c;包含实现者&#xf…

Linux中文件操作

文件由文件内容和文件属性构成&#xff0c;因此对文件的操作就是对文件内容或文件属性的操作。所谓的“打开一个文件”就是将文件的属性或内容加载到内存中&#xff0c;而没有被打开的文件存在于磁盘上。打开的文件称作“内存文件”&#xff0c;未被打开的文件称作“磁盘文件”…

elasticsearch基础总结

最近实习&#xff0c;项目用的elasticseatch做的存储库&#xff0c;但是之前对于es接触的不多&#xff0c;查询语法有些不熟&#xff0c;每次想写个DSL查询时都要gpt或者施展搜索大法&#xff0c;所以索性就自己总结总结&#xff0c;以后忘了也方便查。所以这篇文章会持续更新。…

c++ map对其值排序

无法直接排序,转换成vector<std::pair<string,int>> #include <iostream> #include <map> #include <vector> #include <algorithm>// 用于排序的比较函数 bool compareByValue(const std::pair<std::string, int>& a, const …

PysimpleGUI试用版变更免费版

1、PysimpleGUI试用版&#xff1a; 由于5.0版本之后不是免费的 2、变更版本&#xff1a; 打开pycharm-设置-python解释器&#xff1a;点击 搜索PysimpleGUI-指定版本-选择低于5.0的版本&#xff1a;安装软件包 3、重新运行PysimpleGUI&#xff0c;即可获得免费版&#xff1a;…

Grule前端表单post后端执行grule引擎规则

Grule前端表单post后端执行grule引擎规则 编写前端表单和后端接口 编写test.go执行grule引擎规则 示例都是 go test 执行的测试代码&#xff0c;所以将里面的测试代码去除 由于之前 NumberExponentExample_test.go 已经验证可运行, 所以将 err 的异常处理去除 package mai…

STM32串口接收与发送(关于为什么接收不需要中断而发生需要以及HAL_UART_Transmit和HAL_UART_Transmit_IT的区别)

一、HAL_UART_Transmit和HAL_UART_Transmit_IT的区别 1. HAL_UART_Transmit_IT&#xff08;非阻塞模式&#xff09;&#xff1a; HAL_UART_Transmit_IT 是非阻塞的传输函数&#xff0c;也就是说&#xff0c;当你调用 HAL_UART_Transmit_IT 时&#xff0c;它不会等到数据完全发…

使用R语言优雅的获取任意区域的POI,道路,河流等数据

POI是“Polnt of Information”的缩写&#xff0c;中文可以翻译为“信息点”。是地图上任何非地理意义的有意义的点&#xff0c;如商店&#xff0c;酒吧&#xff0c;加油站&#xff0c;医院&#xff0c;车站等。POI&#xff0c;道路网&#xff0c;河流等是我们日常研究中经常需…

七、docker registry

七、docker registry 7.1 了解Docker Registry 7.1.1 介绍 registry 用于保存docker 镜像&#xff0c;包括镜像的层次结构和元数据。启动容器时&#xff0c;docker daemon会试图从本地获取相关的镜像&#xff1b;本地镜像不存在时&#xff0c;其将从registry中下载该镜像并保…

目标跟踪算法:SORT、卡尔曼滤波、匈牙利算法

目录 1 目标检测 2 卡尔曼滤波 3《从放弃到精通&#xff01;卡尔曼滤波从理论到实践》视频简单学习笔记 3.1 入门 3.2 进阶 3.2.1 状态空间表达式 3.2.2 高斯分布 3.3 放弃 3.4 精通 4 匈牙利算法 5 《【运筹学】-指派问题&#xff08;匈牙利算法&#xff09;》视…

OpenCV-图像阈值

简单阈值法 此方法是直截了当的。如果像素值大于阈值&#xff0c;则会被赋为一个值&#xff08;可能为白色&#xff09;&#xff0c;否则会赋为另一个值&#xff08;可能为黑色&#xff09;。使用的函数是 cv.threshold。第一个参数是源图像&#xff0c;它应该是灰度图像。第二…

【HarmonyOS NEXT】实现Tabs组件的TabBar从左到右依次排列

一、背景 系统提供的Tabs目前只能居中展示&#xff0c;暂不支持居左显示&#xff0c;现有的需求是需要Tabs从左往右排列显示&#xff0c;考虑通过Scroll和Row组件来实现 二、实现思路 通过Scroll和Row组件用来实现一个页签&#xff0c;在onclick事件中通过修改索引值和Tabs组…

16-03、JVM系列之:内存与垃圾回收篇(三)

JVM系列之&#xff1a;内存与垃圾回收篇(三) ##本篇内容概述&#xff1a; 1、执行引擎 2、StringTable 3、垃圾回收一、执行引擎 ##一、执行引擎概述 如果想让一个java程序运行起来&#xff0c;执行引擎的任务就是将字节码指令解释/编译为对应平台上的本地机器指令才可以。 简…

FPGA工作原理、架构及底层资源

FPGA工作原理、架构及底层资源 文章目录 FPGA工作原理、架构及底层资源前言一、FPGA工作原理二、FPGA架构及底层资源 1.FPGA架构2.FPGA底层资源 2.1可编程输入/输出单元简称&#xff08;IOB&#xff09;2.2可配置逻辑块2.3丰富的布线资源2.4数字时钟管理模块(DCM)2.5嵌入式块 …