力扣刷题-哈希表-三数之和

15 三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意: 答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]

思路

本题若采用哈希来解决,在处理去重的时候会比较复杂,所以本题考虑容易理解的双指针法。

拿这个nums数组来举例,首先将数组排序,然后有一层for循环,i从下标0的地方开始,同时定一个下标left 定义在i+1的位置上,定义下标right 在数组结尾的位置上。
依然还是在数组中找到 abc 使得a + b +c =0,我们这里相当于 a = nums[i],b = nums[left],c = nums[right]。
接下来如何移动left 和right呢, 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了,因为数组是排序后了,所以right下标就应该向左移动,这样才能让三数之和小一些。
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了,left 就向右移动,才能让三数之和大一些,直到left与right相遇为止。
时间复杂度:O(n^2)。(有两层循环)
关于去重逻辑的思考可参考:https://www.programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html#%E6%80%9D%E8%B7%AF
写的很详细。

class Solution(object):def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""# 本题的一个复杂之处是 答案中不可以包含重复的三元组# 采用双指针法 result = [] # 存储结果nums = sorted(nums) # 先对nums进行排序 可以方便很多for i in range(len(nums)): # 将i视为a 三数中的第一个数if nums[i] > 0: # 第一个数就大于0return resultif i > 0 and nums[i]==nums[i-1]: # 对a去重 跳过重复的三元组 注意是nums[i]==nums[i-1]continue left = i + 1 # 第一个指针 将left视为b 三数中的第二个数right = len(nums)-1 # 第二个指针 将right视为c 三数中的第三个数while(right > left): # 不能等于 因为要求三个数 若right=left 那就是指向同一个数sum_ = nums[i] + nums[left] + nums[right]if sum_ > 0:right -= 1 # 有点像滑动窗口elif sum_ < 0:left += 1else:result.append([nums[i], nums[left], nums[right]])# 对b去重while right > left and nums[left]==nums[left+1]:left += 1 # left就后移一位# 对c去重while right > left and nums[right]==nums[right-1]:right -= 1# 无论如何 都要移动left和rightleft += 1right -= 1return result

思考

与两数之和的区别:前面两数之和返回的是元素下标(并且题目说明:你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。),而本题三数之和返回的是具体的元素。
所以在python中,可以用集合这种数据集结构来使用哈希法,刚好又是需要索引。所以对于这种两数之和,最好的方法还是哈希法。

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

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

相关文章

由于计算机中丢失msvcp110.dll的解决方法与msvcp110.dll丢失修复方法

相信大家在打开电脑软件或许游戏都有遇到过电脑提示找不到msvcp110.dll文件&#xff0c;导致软件游戏打不开&#xff0c;我们应该怎么办&#xff1f;不用着急&#xff0c;今天小编我分享我找了很久成功解决问题的方法给大家&#xff0c;希望可以帮到各位。 1. 使用DLL修复工具&…

【word】从正文开始设置页码

在写报告的时候&#xff0c;会要求有封面和目录&#xff0c;各占一页。正文从第3页开始&#xff0c;页码从正文开始设置 word是新建的 分出三节&#xff08;封面、目录、正文&#xff09; 布局--->分割符--->分节符--->下一页 这样就能将word分为3节&#xff0c;分…

基于SSM的餐厅点菜管理系统的设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;采用Vue技术开发 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#x…

京东数据产品:8月大家电市场增长类目市场数据分析

上期我们已经分析了大家电市场及市场中的头部类目&#xff0c;从大家电的市场数据可知&#xff0c;整个行业大盘及多数细分市场都呈下滑走势。不过&#xff0c;仍有部分偏向精致生活的电器呈上升走势&#xff0c;如洗烘套装、内衣清洗机、衣物护理机等&#xff0c;下面我们一起…

案例突破——再探策略模式

再探设计模式 一、背景介绍二、 思路方案三、过程1. 策略模式基本概念2. 策略模式类图3. 策略模式基本代码策略类抽象策略类Context类客户端 4. 策略模式还可以进行优化的地方5. 对策略模式的优化&#xff08;配置文件反射&#xff09; 四、总结五、升华 一、背景介绍 在做项目…

多线程(如何理解pthread库)

上一节&#xff0c;我们主要介绍了pthread库中一些常见函数的用法&#xff0c;这节我们主要分析一下pthread库到底是什么&#xff1f; 什么是库 我们之前提过&#xff0c;在每一个linux平台下&#xff0c;必定会存在对应的pthread库 它存在于/lib64这个路径底下 换句话说&am…

辅助驾驶功能开发-测试篇(2)-真值系统介绍

1 真值系统概述 1.1 真值评测系统核心应用 快速构建有效感知真值,快速完成感知性能评估,快速分析感知性能缺陷。 主要应用场景包括: 1. 感知算法开发验证: 在算法开发周期中,评测结果可以作为测试报告的一部分,体现算法性能的提升。 2. 遴选供应…

我的企业证书是正常的但是下载应用app到手机提示无法安装“app名字”无法安装此app,因为无法验证其完整性解决方案

我的企业证书是正常的但是下载应用app到手机提示无法安装“app名字”无法安装此app&#xff0c;因为无法验证其完整性解决方案 首先&#xff0c;确保您从可信任的来源下载并安装企业开发者签名过的应用程序。如果您不确定应用程序的来源&#xff0c;建议您联系应用程序提供者…

linux下查找文件的相关命令

linux下查找文件的相关命令 运行环境&#xff1a;centos7 参考来源&#xff1a;man、鸟哥入门书籍 一、脚本文件查找&#xff1a;which/type 1. which man手册描述&#xff1a; 返回当前环境可以被执行的文件&#xff08;或链接&#xff09;的路径。搜索PATH变量匹配参数中…

【PostgreSQL】【存储管理】表和元组的组织方式

外存管理负责处理数据库与外存介质(PostgreSQL8.4.1版本中只支持磁盘的管理操作)的交互过程。在PostgreSQL中&#xff0c;外存管理由SMGR(主要代码在smgr.c中)提供了对外存的统一接口。SMGR负责统管各种介质管理器&#xff0c;会根据上层的请求选择一个具体的介质管理器进行操作…

十四天学会C++之第二天(函数和库)

1. 函数的定义和调用 在C中&#xff0c;函数是组织和结构化代码的关键工具之一。它们允许您将一段代码封装成一个可重复使用的模块&#xff0c;这有助于提高代码的可读性和维护性。 为什么使用函数&#xff1f; 函数在编程中的作用不可小觑。它们有以下几个重要用途&#xf…

WEB3 solidity 带着大家编写测试代码 操作订单 创建/取消/填充操作

好 在我们的不懈努力之下 交易所中的三种订单函数已经写出来了 但是 我们只是编译 确认了 代码没什么问题 但还没有实际的测试过 这个测试做起来 其实就比较的麻烦了 首先要有两个账号 且他们都要在交易所中有存入 我们还是先将 ganache 的虚拟环境启动起来 然后 我们在项目…

EasyX图形库note4,动画及键盘交互

大家好&#xff0c;这里是Dark Flame Master&#xff0c;专栏从这篇开始就会变得很有意思&#xff0c;我们可以利用今天所学的只是实现很多功能&#xff0c;同样为之后的更加好玩的内容打下基础&#xff0c;从这届开始将会利用所学的知识制作一些小游戏&#xff0c;废话不多说&…

第一百六十二回 PopupMenuButton组件

文章目录 概念介绍使用方法示例代码 我们在上一章回中介绍了Sliver综合示例相关的内容&#xff0c;本章回中将介绍 PopupMenuButton组件.闲话休提&#xff0c;让我们一起Talk Flutter吧。 概念介绍 我们在本章回中介绍的PopupMenuButton组件位于AppBar右侧&#xff0c;通常显…

MacOS怎么安装Nacos(附带:Windows系统)

MacOS安装Nacos&#xff08;一定要配置JDK的环境变量&#xff0c;后面告诉你为什么&#xff1f;&#xff09; &#xff08;1&#xff09;进入Nacos官网&#xff0c;前往githubhomehomehttp://nacos.io/zh-cn/ &#xff08;2&#xff09;点击右下角的releases 然后点击Tags 选择…

Linux实用操作(固定IP、进程控制、监控、文件解压缩)

目录 一、快捷键 1、ctrl c强制停止 2、ctrl d退出或登出 3、历史命令搜索history 4、光标移动快捷键 5、清屏 二、软件安装 1、CentOS的yum命令 2、Ubantu的apt命令 三、systemctl命令 四、软连接 五、日期、时区 1、date命令 2、修改Linux时区为东八区 3、nt…

智慧公厕整体解决方案,厕所革命实施方案的范本

随着城市化进程的不断加快&#xff0c;智慧城市应用正成为未来城市发展的重要方向。其中&#xff0c;智慧公厕作为城市基础设施的重要组成部分&#xff0c;其建设范本已经成为各建设中的智慧城市不可或缺的重要内容。那么&#xff0c;如何打造智慧公厕整体解决方案&#xff1f;…

servlet 线程模型 异步

在 servlet 3.0 之前&#xff0c;请求与线程的对应关系是1:1&#xff0c;对应jvm与操作系统的线程的关系。 servlet 3.0 https://jcp.org/en/jsr/detail?id315 从 servlet 3.0 开始&#xff0c;开始有了异步相关功能&#xff0c;作为 Java EE 6 的新功能。 容器线程池与业务线…

王杰国庆作业day6

服务器 #include <stdio.h> #include <string.h> #include <stdlib.h> #include <my_head.h> #define PORT 2324 //端口号 #define IP "192.168.10.107" //本机IP int main(int argc, const char *argv[]) {sqlite3* d…

宠物医院必备,介绍一款宠物疫苗接种管理软件

在当今社会&#xff0c;养宠物已经成为越来越多人的生活方式&#xff0c;宠物疫苗接种已是宠物医院的重要工作&#xff0c;但是目前绝大多数的宠物医院对疫苗接种的管理&#xff0c;还是采取人工登记方式&#xff0c;不仅效率低下&#xff0c;而且无法做到疫苗接种到期自动提醒…