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

【面试经典150 | 双指针】三数之和

文章目录

  • 写在前面
  • Tag
  • 题目来源
  • 题目解读
  • 解题思路
    • 方法一:暴力枚举
    • 方法二:双指针
  • 写在最后

写在前面

本专栏专注于分析与讲解【面试经典150】算法,两到三天更新一篇文章,欢迎催更……

专栏内容以分析题目为主,并附带一些对于本题涉及到的数据结构等内容进行回顾与总结,文章结构大致如下,部分内容会有增删:

  • Tag:介绍本题牵涉到的知识点、数据结构;
  • 题目来源:贴上题目的链接,方便大家查找题目并完成练习;
  • 题目解读:复述题目(确保自己真的理解题目意思),并强调一些题目重点信息;
  • 解题思路:介绍一些解题思路,每种解题思路包括思路讲解、实现代码以及复杂度分析;
  • 知识回忆:针对今天介绍的题目中的重点内容、数据结构进行回顾总结。

Tag

【双指针】【数组】


题目来源

面试经典150 | 15. 三数之和


题目解读

给你一个整数数组 nums,找出其中所有同时满足以下条件的三元组:

  • nums[i] + nums[j] + nums[k] = 0
  • i != jj != kk != i

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


解题思路

方法一:暴力枚举

找出和为 0 的三元组,最容易想到的方法就是枚举所有可能的三元组,然后求和。但是答案中不允许包含重复的三元组,因此想到先进行排序处理,将数组 nums 中所有重复的元素放在一起,方便后续的去重处理,这一步也是后续几种方法的必要的步骤。

枚举所有可能的三元组的方法最容易想到,但是时间复杂度为 O ( n 3 ) O(n^3) O(n3) n n n 为数组 nums 的长度,本题的数据量达到 1 0 3 10^3 103,必然超时。

方法二:双指针

为了应对重复答案的情况出现,我们首先对数组 nums 进行排序处理。

接着,枚举第一个加数 nums[i],剩下两个加数的查找我们可以使用 两数之和 中双指针的思想来解决,具体地:

  • 枚举第一个加数 nums[i]
  • 如果 i >= 1nums[i] = nums[i-1],说明数字 nums[i] 已经作为第一个元素了, 我们需要则继续枚举下一个位置的 nums[i] 作为第一个加数;
  • 否则,利用双指针查找第二、三个加数:
  • 维护双指针 jk 分别指向需要查找的第二、三个数字位置,初始化 j = i + 1k = n - 1
  • 如果 nums[i] + nums[j] + nums[k] > 0,则 --k
  • 如果 nums[i] + nums[j] + nums[k] < 0,则 ++j
  • 如果 nums[i] + nums[j] + nums[k] = 0,则当前的 {nums[i], nums[j], nums[k]} 为一个满足条件的三元组并加入到 答案数组 ret 中,并且右移 j 到下一个与数字 nums[j] 的位置,左移 k 到下一个与数字 nums[k] 的位置 。

最后,返回答案数组 ret

优化

本题中还有一些可以优化的地方:

  • 如果 n < 3,即数组的长度小于 3,不会有三个数;
  • 如果排序后的 nums[0] > 0,表明数组中的所有数字都大于 0,一定不会有和为 0 的三元组;
  • 如果排序后的 nums[n-1] > 0,表明数组中的所有数字都小于 0,一定不会有和为 0 的三元组;

加上以上的优化代码,双指针解法就是最优的解法了。

实现代码

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;int n = nums.size();sort(nums.begin(), nums.end());if(n < 3 || nums[0] > 0 || nums[n-1] < 0){return ret;}int i, j, k;for(i = 0; i < n-2; ++i){if(i && nums[i] == nums[i-1]){continue;}j = i + 1;k = n - 1;while(j < k){int target = nums[i] + nums[j] + nums[k];if(target > 0){--k;}else if(target < 0){++j;}else{ret.push_back({nums[i], nums[j], nums[k]});++j;--k;while(j < k && nums[j] == nums[j-1]) ++j;while(j < k && nums[k] == nums[k + 1]) --k;}}}return ret;}
};

复杂度分析

时间复杂度: O ( n 2 ) O(n^2) O(n2) n n n 为数组 nums 的长度,枚举第一个加数的时间复杂度为 O ( n ) O(n) O(n),利用双指针查找满足条件的第二、三个加数的时间复杂度为 O ( n ) O(n) O(n),因此总的时间复杂度为 O ( n 2 ) O(n^2) O(n2)

空间复杂度: O ( l o g n ) O(logn) O(logn),双指针解法仅使用有限个额外空间,排序占用的额外空间为 O ( l o g n ) O(logn) O(logn),因此空间复杂度为 O ( l o g n ) O(logn) O(logn)

写在最后

如果文章内容有任何错误或者您对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法,欢迎评论区交流。

最后,感谢您的阅读,如果感到有所收获的话可以给博主点一个 👍 哦。

相关文章:

【面试经典150 | 双指针】三数之和

文章目录 写在前面Tag题目来源题目解读解题思路方法一&#xff1a;暴力枚举方法二&#xff1a;双指针 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对…...

现代卷积网络实战系列3:PyTorch从零构建AlexNet训练MNIST数据集

1、AlexNet AlexNet提出了一下5点改进&#xff1a; 使用了Dropout&#xff0c;防止过拟合使用Relu作为激活函数&#xff0c;极大提高了特征提取效果使用MaxPooling池化进行特征降维&#xff0c;极大提高了特征提取效果首次使用GPU进行训练使用了LRN局部响应归一化&#xff08…...

Django系列:Django应用(app)的创建与配置

Django系列 Django应用&#xff08;app&#xff09;的创建与配置 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article…...

Linux查看程序和动态库依赖的动态库

一. 前言 在一些时候&#xff0c;我们需要知道一个程序或者动态库所依赖的动态库有哪些。比如&#xff0c;当我们运行一个程序的时候&#xff0c;发现可能会报错&#xff0c;提示找不到某个符号&#xff0c;这时我们就需要知道程序依赖了什么库&#xff0c;从而添加对应需要的动…...

vue3 无法使用pnpm安装依赖 或 Cannot find module preinstall.js

创建.npmrc文件在根目录 shamefully-hoisttrue auto-install-peerstrue strict-peer-dependenciesfalse删除 node_modules 和 pnpm-lock.yaml 文件 重新 pnpm i 就可以啦...

C/C++连接数据库,包含完整代码。

C/C连接数据库 本篇文章意在简洁明了的在linux环境下使用C/C连接远程数据库&#xff0c;并对数据库进行增删查改等操作。我所使用的环境是centos7&#xff0c;不要环境除环境配置外&#xff0c;代码是大同小异的。完整代码在最底部&#xff01;&#xff01;&#xff01; 1.前…...

AUTOSAR词典:CAN驱动Mailbox配置技术要点全解析

AUTOSAR词典&#xff1a;CAN驱动Mailbox配置技术要点全解析 前言 首先&#xff0c;请问大家几个小小问题&#xff0c;你清楚&#xff1a; AUTOSAR框架下的CAN驱动关键词定义吗&#xff1f;是不是有些总是傻傻分不清楚呢&#xff1f;CAN驱动Mailbox配置过程中有哪些关键配置参…...

C语言 coding style

头文件 The #define Guard #define的保护文件的唯一性&#xff0c;防止被多重包含 格式 : <PROJECT>_< FILE>_H_ PROJECT : XS FILE : MV_CTR 头文件的包含顺序 C System FilesOther LibrariesUser LibraryConditional include 作用域 局部变量 -变量定义时需要…...

Python办公自动化之PDF

Python操作PDF 1、Python操作PDF概述2、批量拆分3、批量合并4、提取内容(文字)5、提取内容(表格)6、提取图片7、PDF添加水印8、加密与解密1、Python操作PDF概述 Python操作PDF主要有两个库:PyPDF2和pdfplumber PyPDF2是一个用于处理PDF文件的Python第三方库 官网文档参考:…...

【每日一题Day331】LC2560打家劫舍 IV | 二分查找 + 贪心

打家劫舍 IV【LC2560】 沿街有一排连续的房屋。每间房屋内都藏有一定的现金。现在有一位小偷计划从这些房屋中窃取现金。 由于相邻的房屋装有相互连通的防盗系统&#xff0c;所以小偷 不会窃取相邻的房屋 。 小偷的 窃取能力 定义为他在窃取过程中能从单间房屋中窃取的 最大金额…...

JVM 参数详解

GC有两种类型&#xff1a;Scavenge GC 和Full GC 1、Scavenge GC 一般情况下&#xff0c;当新对象生成&#xff0c;并且在Eden申请空间失败时&#xff0c;就会触发Scavenge GC&#xff0c;堆的Eden区域进行GC&#xff0c;清除非存活对象&#xff0c;并且把尚且存活的对象移动到…...

uni-app获取地理位置

在uni-app中&#xff0c;可以通过uni.getLocation()方法获取地理位置。具体步骤如下&#xff1a; 在uni-app项目中的manifest.json文件中&#xff0c;添加需要获取地理位置的权限&#xff1a; {"mp-weixin": {"appid": "...","permission…...

Learn Prompt-Prompt 高级技巧:思维链 Chain of Thought Prompting

Jason Wei等作者对思维链的定义是一系列的中间推理步骤&#xff08; a series of intermediate reasoning steps &#xff09;。目的是为了提高大型语言模型&#xff08;LLM&#xff09;进行复杂推理的能力。 思维链通常是伴随着算术&#xff0c;常识和符号推理等复杂推理任务出…...

Vim编辑器使用入门

目录 一、Vim 编辑器基础操作 二、Vim 编辑器进阶操作 三、Vim 编辑器高级操作 四、Vim 编辑器文件操作 五、Vim 编辑器文件管理 六、Vim 编辑器进阶技巧 七、Vim 编辑器增强功能 Vim的三种工作模式 一、Vim 编辑器基础操作 1.移动光标 - 光标的移动控制 移动光标有两…...

早餐与风景

来吧&#xff0c;我用流水账描述下这一天。 时维九月&#xff0c;北京的早上有点冷&#xff0c;因为今天有个市场活动要去支撑&#xff0c;按照会议时间的要求&#xff0c;我需要在早上7点半就赶到会场&#xff0c;所以昨天晚上我加班到凌晨处理完了今天要给出去的材料&#xf…...

常用python代码串

记录新疆出差期间的一些代码 打开yaml文件python中的专有名词ctrlc 打开yaml文件 with open(/home/cyun/文档/cotton_ws/src/control/scripts/ControlParameter.yaml, r) as file:yaml_data yaml.load(file, Loaderyaml.FullLoader)后面发现像这种打开文件的最好是try一下 p…...

电脑桌面透明便签软件是哪个?

在现代快节奏的工作环境中&#xff0c;许多上班族都希望能够在电脑桌面上方便地记录工作资料、重要事项、工作流程等内容。为了解决这个问题&#xff0c;一款优秀的电脑桌面便签软件是必不可少的。在选择桌面便签软件时&#xff0c;许多用户也希望便签软件能够与电脑桌面壁纸相…...

Git创建干净分支,本地操作不依赖任何分支

clone远程项目: git clone gittest.git查看分支: git branch -a创建新分支: git checkout --orphan test, 返回Switched to a new branch test删除当前项目文件夹下所有文件: git rm -rf .提交变更: git commit -m "new branch for test"查看分支: git branch -a, 发…...

sqlmap tamper脚本编写

文章目录 tamper脚本是什么&#xff1f;指定tamper脚本运行sqlmap安全狗绕过tamper脚本 tamper脚本是什么&#xff1f; SQLMap 是一款SQL注入神器&#xff0c;可以通过tamper 对注入payload 进行编码和变形&#xff0c;以达到绕过某些限制的目的。但是有些时候&#xff0c;SQLM…...

5.5V-65V Vin同步降压控制器,具有线路前馈SCT82630DHKR

描述&#xff1a; SCT82630是一款65V电压模式控制同步降压控制器&#xff0c;具有线路前馈。40ns受控高压侧MOSFET的最小导通时间支持高转换比&#xff0c;实现从48V输入到低压轨的直接降压转换&#xff0c;降低了系统复杂性和解决方案成本。如果需要&#xff0c;在低至6V的输…...

通用汽车IT部门裁员600人,为AI人才腾空间,软件团队变革进行时

通用汽车IT部门裁员600人&#xff0c;AI人才成新宠 通用汽车证实已对其IT部门进行裁员&#xff0c;约600名领薪员工&#xff08;占比10%以上&#xff09;被裁&#xff0c;目的是清除专业知识不再适用的员工&#xff0c;为具有AI背景的人员腾出空间。公司表示这是面向未来做好准…...

Pytorch图像去噪实战(七十四):Kubernetes部署图像去噪服务,实现容器编排和弹性扩展

Pytorch图像去噪实战(七十四):Kubernetes部署图像去噪服务,实现容器编排和弹性扩展 一、问题场景:Docker Compose够用,但多服务扩展开始吃力 前面我们用 Docker Compose 部署了图像去噪服务。 Compose 对单机部署非常好用,但当项目变复杂后,会遇到: 多台机器部署困难…...

PDPI Spec:规格驱动开发协议,让AI编程告别“氛围编码”

1. 项目概述&#xff1a;从“感觉对了”到“规格对了”在软件开发的江湖里&#xff0c;我们可能都经历过这样的场景&#xff1a;产品经理丢过来一个模糊的需求&#xff0c;开发同学凭着一腔热血和“感觉对了”的直觉&#xff0c;一头扎进代码里。几周后&#xff0c;功能上线了&…...

告别编译地狱!树莓派4B上快速部署face_recognition库的三种方法(含OpenCV轻量安装)

树莓派4B人脸识别开发环境快速部署指南 每次在树莓派上配置人脸识别开发环境&#xff0c;最让人头疼的就是漫长的编译等待和层出不穷的依赖问题。特别是OpenCV这个计算机视觉领域的"瑞士军刀"&#xff0c;完整编译动辄需要数小时&#xff0c;稍有不慎就会前功尽弃。本…...

3步终极指南:用开源TCC-G15彻底解决Dell G15散热难题

3步终极指南&#xff1a;用开源TCC-G15彻底解决Dell G15散热难题 【免费下载链接】tcc-g15 Thermal Control Center for Dell G15 - open source alternative to AWCC 项目地址: https://gitcode.com/gh_mirrors/tc/tcc-g15 你是否正在为Dell G15笔记本的过热问题而烦恼…...

FanControl终极指南:5步解决Windows风扇噪音与过热难题

FanControl终极指南&#xff1a;5步解决Windows风扇噪音与过热难题 【免费下载链接】FanControl.Releases This is the release repository for Fan Control, a highly customizable fan controlling software for Windows. 项目地址: https://gitcode.com/GitHub_Trending/f…...

如何用自动化脚本解放双手:淘宝淘金币全任务一键完成指南

如何用自动化脚本解放双手&#xff1a;淘宝淘金币全任务一键完成指南 【免费下载链接】taojinbi 淘宝淘金币自动执行脚本&#xff0c;包含蚂蚁森林收取能量&#xff0c;芭芭农场全任务&#xff0c;解放你的双手 项目地址: https://gitcode.com/gh_mirrors/ta/taojinbi 还…...

LabVIEW数字IO编程避坑指南:单点采样、连续采样到底怎么选?NI-MAX测试面板帮你验证

LabVIEW数字IO编程实战&#xff1a;采样模式选择与NI-MAX验证全攻略 在工业自动化测试领域&#xff0c;LabVIEW的数字IO模块是最基础也最常用的功能之一。许多工程师在初次接触数字IO编程时&#xff0c;往往会被各种采样模式搞得晕头转向——单点采样、N采样、连续采样&#xf…...

从临床试验到互联网AB测试:边缘结构模型(MSM)如何解决你的‘时变混杂’难题

从临床试验到互联网AB测试&#xff1a;边缘结构模型如何破解动态混杂困局 当我们在互联网产品中测试一个新功能对用户留存率的影响时&#xff0c;常常会遇到一个棘手的问题&#xff1a;用户的行为会随着时间不断变化。比如&#xff0c;早期接触新功能的用户可能因为新鲜感而产生…...

基于RAG与MCP协议构建实时新闻AI助手:newsmcp项目实战解析

1. 项目概述&#xff1a;一个让AI“读新闻”的智能工具最近在折腾AI应用开发的朋友&#xff0c;可能都绕不开一个核心问题&#xff1a;如何让大语言模型&#xff08;LLM&#xff09;获取并理解最新的、模型训练数据之外的信息&#xff1f;比如&#xff0c;你想让ChatGPT帮你分析…...