当前位置: 首页 > news >正文

三数之和(双指针)

15. 三数之和 - 力扣(LeetCode)

题目描述

给你一个整数数组 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 。

题解

整体思路

如图所示,代码的整理思路是 

  • 对数组进行排序,使用指针i遍历a,指针left遍历b,指针遍历c。遍历时,固定指针i,之后使用双指针法遍历b与c,
  • 若nums[i]+nums[left]+nums[right]>0,则right--
  • 若nums[i]+nums[left]+nums[right]<0,则left++

去重

由于数组中有重复元素,而题目中要求的结果是不重复的三元组,因此要对a、b、c进行去重,需要注意的是,去重指的是单独的a或者单独的b或者单独的c不能重复,而不是指a与b不能相同

关于对a的去重

对a进行去重时,必须使用以下语句进行判断是否重复

nums[i]==nums[i-1]

不能使用

nums[i]==nums[i+1]

因为,指针i遍历的是a,指针left紧跟i指针后,遍历的是b,如果使用nums[i]==nums[i+1]来判断是否重复,就相当于判断nums[i]与nums[left]是否相等,

三元组[-1,-1,2],i指针指向-1,left指向-1,right指向2,如下图所示,如果使用nums[i]==nums[i+1]进行去重,很显然会错过这个符合条件的三元组

对b和c的去重

除此以外,对b和c的去重,必须要先确定b和c的值之后再进行去重,而不能使用以下代码逻辑,先对b和c进行去重,之后再确定b和c的值,因为这样会错过三元组[0,0,0]的结果

while(l<r)
{//不能在这里对b和c进行去重while(l<r && nums[r]==nums[r-1])r--;while(l<r && nums[l]==nums[l+1])l++;int sum=nums[i]+nums[l]+nums[r];if(sum>0)r--;else if(sum<0)l++;else{res.emplace_back(vector<int>{nums[i],nums[l],nums[r]});r--;l++;}}

代码

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {//对数组进行排序后才能使用双指针sort(nums.begin(),nums.end());int n=nums.size();vector<vector<int>> res;for(int i=0;i<n;i++)//固定a{if(nums[i]>0)return res;//对a进行去重if(i>0 && nums[i]==nums[i-1])continue;//寻找b与cint l=i+1,r=n-1;while(l<r){int sum=nums[i]+nums[l]+nums[r];if(sum>0)r--;else if(sum<0)l++;else{//确定b和c的值res.emplace_back(vector<int>{nums[i],nums[l],nums[r]});//对b和c进行去重while(l<r && nums[r]==nums[r-1])r--;while(l<r && nums[l]==nums[l+1])l++;r--;l++;}}}return res;}
};

相关文章:

三数之和(双指针)

15. 三数之和 - 力扣&#xff08;LeetCode&#xff09; 题目描述 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三…...

Linux-bluetooth蓝牙

蓝牙配对和蓝牙连接 蓝牙配对是指在两个蓝牙设备之间建立一种安全的关系&#xff0c;以确保只有已经通过授权的设备才能进行通信。在蓝牙配对过程中&#xff0c;设备之间将共享一个加密密钥&#xff0c;用于保护数据传输的安全性。通常需要在设备上输入一个PIN码或者进行手动确…...

mediasoup webrtc音视频会议搭建

环境ubuntu22.10 nvm --version 0.33.11 node -v v16.20.2 npm -v 8.19.4 node-gyp -v v10.0.1 python3 --version Python 3.10.7 python with pip: sudo apt install python3-pip gcc&g version 12.2.0 (Ubuntu 12.2.0-3ubuntu1) Make 4.2.1 npm install mediasoup3 sudo …...

【操作系统】操作系统的大端模式和小端模式

什么是大端模式、小端模式&#xff1f; 所谓的大端模式&#xff0c;是指数据的低位保存在内存的高地址中&#xff0c;而数据的高位保存在内存的低地址中&#xff1b; 所谓的小端模式&#xff0c;是指数据的低位保存在内存的低地址中&#xff0c;而数据的高位保存在内存的高地…...

Oracle(13)Maintaining Data Integrity

目录 一、基础知识 1、Data Integrity 数据库的完整性 2、Types of Constraints 约束类型 3、Constraint States 约束状态 4、Guidelines for Constraints 约束准则 二、基础操作 1、Enabling Constraints 启用约束 2、命令方式创建约束 3、修改表创建的约束 4、删除约…...

工程(十二)Ubuntu20.04LSD_SLAM运行

博主创建了一个科研互助群Q&#xff1a;772356582&#xff0c;欢迎大家加入讨论。这是一个科研互助群&#xff0c;主要围绕机器人&#xff0c;无人驾驶&#xff0c;无人机方面的感知定位&#xff0c;决策规划&#xff0c;以及论文发表经验&#xff0c;以方便大家很好很快的科研…...

跨境电商,用指纹浏览器还是VPS?有何区别?

目前做跨境电商的小伙伴基本都是选择vps或者指纹浏览器来防关联。不过随着指纹浏览器的普及&#xff0c;越来越多人选择使用指纹浏览器&#xff0c;还没了解过指纹浏览器的小伙伴可能还在犹豫&#xff0c;vps和指纹浏览器到底哪个更好呢&#xff1f; Vps就是一个虚拟服务器&…...

R语言piecewiseSEM结构方程模型在生态环境领域实践技术应用

结构方程模型&#xff08;Sructural Equation Modeling&#xff0c;SEM&#xff09;可分析系统内变量间的相互关系&#xff0c;并通过图形化方式清晰展示系统中多变量因果关系网&#xff0c;具有强大的数据分析功能和广泛的适用性&#xff0c;是近年来生态、进化、环境、地学、…...

一站式解决方案:体验亚马逊轻量服务器/VPS的顶级服务与灵活性

文章目录 一、什么是轻量级服务器/VPS 二、服务器创建步骤 三、服务器连接客户端(私钥登录) 四、使用服务器搭建博客网站 五、个人浅解及总结 一、什么是轻量级服务器/VPS 亚马逊推出的轻量级服务器/VPS&#xff1a;是一种基于云计算技术的虚拟服务器解决方案。它允许用户…...

pda条码二维码扫描数据采集安卓手持终端扫码热敏标签打印一体机

HT800新一代移动物联终端是深圳联强优创信息科技有限公司自主研发的基于Android11操作系统的高性能、高可靠的工业级手持数据终端&#xff0c;能与其它设备进行无线通讯&#xff0c;提供良好的操作界面&#xff0c;支持条码扫描、RFID读写&#xff08;NFC&#xff09;、GPS定位…...

白上这么多年班,才知道数据可视化这么简单

写编程整理数据、做数据可视化分析&#xff0c;不仅难度大、易僵化&#xff0c;还效率低&#xff0c;不能及时响应业务的数据分析需求。那怎么办&#xff1f;换个BI数据可视化工具&#xff0c;套用BI方案&#xff0c;数据分析模型、BI数据可视化分析报表都一应俱全&#xff0c;…...

伊朗黑客对以色列科技和教育领域发起破坏性网络攻击

导语 近期&#xff0c;以色列的高等教育和科技领域遭受了一系列破坏性的网络攻击。这些攻击始于2023年1月&#xff0c;旨在部署以前未记录的数据清除恶意软件。在最近的攻击中&#xff0c;攻击者试图窃取个人身份信息和知识产权等敏感数据。本文将介绍这些攻击的具体细节&#…...

前端初始化项目切换镜像命令

不切换成国内镜像容易出现&#xff1a; idealTree:moni: sill idealTree buildDeps 一直卡着 命令如下&#xff1a; 一、 npm config get registry&#xff0c;查看当前镜像地址 二、出现 https://registry.npmjs.org/ 则表示在国外 三、使用以下命令切换成国内阿里…...

Springboot中解析JSON字符串(jackson库ObjectMapper解析JSON字符串)

1、ObjectMapper与JSONObject比较 1、ObjectMapper属于jackson库的一部分,JSONObject属于alibaba的fastjson&#xff0c;两者各有优劣&#xff0c;可根据自己的系统环境选择使用哪种技术。 2、目前来看&#xff0c;Jackson社区相对活跃&#xff0c;Spring MVC和Spring Boot都…...

QtC++与QToolButton详解

介绍 QToolButton 是 Qt 中的一个控件类&#xff0c;用于创建工具按钮&#xff0c;它有以下主要作用和特点&#xff1a; 工具按钮&#xff1a; QToolButton 用于创建工具按钮&#xff0c;允许用户执行各种操作&#xff0c;如启动功能、弹出菜单、打开文件等。工具按钮通常用于…...

Vue创建浅层响应式数据

shallowReactive&#xff1a;只处理对象第一层数据的响应式&#xff08;浅响应式&#xff09;。 shallowRef&#xff1a;只处理基本数据类型的响应式&#xff0c;不处理对象类型的响应式。 shallowReactive 适用于&#xff1a;如果有一个对象类型的数据&#xff0c;结构比较深…...

【Python 千题 —— 基础篇】判断列表是否为空

题目描述 题目描述 编写一个程序&#xff0c;给出一个列表&#xff0c;判断该列表是否为空。如果该列表为空&#xff0c;输出 “The list is empty”&#xff1b;如果不为空&#xff0c;输出 “The list is not empty”。 输入描述 无输入。 输出描述 根据该列表是否为空…...

基于Java+SpringBoot+Mybaties-plus+Vue+ElementUI 失物招领小程序 设计与实现

一.项目介绍 失物招领小程序 用户登录、忘记密码、退出系统 发布失物 和 发布招领 查看我发布的失物和招领信息 失捡物品模块可以查看和搜索所有用户发布的信息。 二.环境需要 1.运行环境&#xff1a;java jdk1.8 2.ide环境&#xff1a;IDEA、Eclipse、Myeclipse都可以&#…...

找到【SVM】中最优的惩罚项系数C

因为本来SVM是想找到间隔最大的分割面&#xff0c;所以C越大&#xff0c;SVC会选择边际更小的&#xff0c;能够更好的分类所有训练点的决策边界&#xff0c;不过模型的训练时间也会越长。如果C的设定值较小&#xff0c;那SVC会尽量最大化边界&#xff0c;决策功能会更简单&…...

Go 面向对象,多态

面向对象 工程结构 新建一个oop.go package _oop // Package _oop 引用名称import ("fmt""strconv" )// GIRL 常量 const (// GIRL 自增GIRL Gender iotaFIRSTSECONDTHIRD )type Gender uint8 // 无符号的8位整数类型// User 结构体 type User struct…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)

在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...

DiscuzX3.5发帖json api

参考文章&#xff1a;PHP实现独立Discuz站外发帖(直连操作数据库)_discuz 发帖api-CSDN博客 简单改造了一下&#xff0c;适配我自己的需求 有一个站点存在多个采集站&#xff0c;我想通过主站拿标题&#xff0c;采集站拿内容 使用到的sql如下 CREATE TABLE pre_forum_post_…...

CSS3相关知识点

CSS3相关知识点 CSS3私有前缀私有前缀私有前缀存在的意义常见浏览器的私有前缀 CSS3基本语法CSS3 新增长度单位CSS3 新增颜色设置方式CSS3 新增选择器CSS3 新增盒模型相关属性box-sizing 怪异盒模型resize调整盒子大小box-shadow 盒子阴影opacity 不透明度 CSS3 新增背景属性ba…...

ArcPy扩展模块的使用(3)

管理工程项目 arcpy.mp模块允许用户管理布局、地图、报表、文件夹连接、视图等工程项目。例如&#xff0c;可以更新、修复或替换图层数据源&#xff0c;修改图层的符号系统&#xff0c;甚至自动在线执行共享要托管在组织中的工程项。 以下代码展示了如何更新图层的数据源&…...