当前位置:网站首页>【leetcode】剑指 Offer II 007. 数组中和为 0 的三个数(双指针)
【leetcode】剑指 Offer II 007. 数组中和为 0 的三个数(双指针)
2022-08-03 19:24:00 【friedrichor】
剑指 Offer II 007. 数组中和为 0 的三个数
给定一个包含 n 个整数的数组 nums
,判断 nums
中是否存在三个元素 a ,b ,c ,使得 a + b + c = 0 ?请找出所有和为 0 且 不重复 的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
示例 2:
输入:nums = []
输出:[]
示例 3:
输入:nums = [0]
输出:[]
提示:
- 0 < = n u m s . l e n g t h < = 3000 0 <= nums.length <= 3000 0<=nums.length<=3000
- − 1 0 5 < = n u m s [ i ] < = 1 0 5 -10^5 <= nums[i] <= 10^5 −105<=nums[i]<=105
题解
这道题其实是剑指 Offer II 006. 排序数组中两个数字之和 的进阶版,可以参考上道题的思路来进一步解决这道题。
方法一:穷举
具体实现略。
方法二:固定一个值 + 双指针
这个方法可以先看剑指 Offer II 006. 排序数组中两个数字之和 的【方法三:双指针】
首先把 nums
按从小到大排列,固定第一个值 i,0 - nums[i]
即为上一题的 target
,然后剩下两个数的查找方法就用上一题双指针的方法即可。此外,这里还要注意去重的问题,因为题目中要求是 不重复 的三元组。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
nums.sort() # 从小到大排序
length = len(nums)
for i in range(length - 2):
if i > 0 and nums[i] == nums[i-1]: # 去重
continue
low = i + 1
high = length - 1
while low < high:
if nums[i] + nums[low] + nums[high] == 0:
res.append([nums[i], nums[low], nums[high]])
while low < high: # 去重
low += 1
if nums[low] != nums[low - 1]:
break
while low < high: # 去重
high -= 1
if nums[high] != nums[high + 1]:
break
elif nums[i] + nums[low] + nums[high] > 0:
high -= 1
else:
low += 1
return res
在上一道题中还有个二分查找的方法,不过这题用二分法就需要遍历两次,且去重等条件的实现有些复杂,不推荐使用。
边栏推荐
- if/else或switch替换为Enum
- redis常用命令,HSET,XADD,XREAD,DEL等
- 钱江摩托某型号产品ECU货不对版 消费者知情权应如何保障?
- Teach you to locate online MySQL slow query problem hand by hand, package teaching package meeting
- LeetCode 952. 按公因数计算最大组件大小
- Unity gets the actual coordinates of the ui on the screen under the canvas
- 网络协议-TCP、UDP区别及TCP三次握手、四次挥手
- 线上一次JVM FullGC搞得整晚都没睡,彻底崩溃
- 1-php学习笔记之数据类型
- Execute the mysql script file in the docker mysql container and solve the garbled characters
猜你喜欢
MySQL master-slave, 6 minutes you master!
Zhong Hua, senior architect of Ali: China-Taiwan strategic thinking and architecture practice; including internal implementation manual
盲僧发现了华点——教你如何使用API接口获取数据
丙二醇二乙酸酯(Propylene Glycol Diacetate)
APT级全面免杀与企业纵深防御体系的红蓝对抗
Network protocol-TCP, UDP difference and TCP three-way handshake, four wave
系统太多,多账号互通如何实现?
[Notes] Introduction to machine learning
LeetCode 622. 设计循环队列
图像超分——Real-ESRGAN快速上手
随机推荐
手把手教你定位线上MySQL慢查询问题,包教包会
设备树基本原理与操作方法
CentOS 7 安装mysql
【统计机器学习】线性回归模型
pg_memory_barrier_impl in Postgresql and C's volatile
Teach you to locate online MySQL slow query problem hand by hand, package teaching package meeting
云图说丨初识华为云微服务引擎CSE
The addition and subtraction of the score of the force deduction brush question (a daily question 7/27)
dpkg强制安装软件
X86函数调用模型分析
Unity获取canvas 下ui 在屏幕中的实际坐标
阿里巴巴政委体系-第九章、阿里政委启示录
go语言实现导出string字符串到文件中
Matlab论文插图绘制模板第42期—气泡矩阵图(相关系数矩阵图)
建模该从哪一步开始?给你分析,给零基础的你一些学习建议
Alibaba senior experts create a learning architecture from scratch, including Alibaba's internal technology stack PPT, PFD actual combat
C#将位图旋转90度
Standard C language learning summary 11
mysql跨库关联查询(dblink)
SQL server 实现触发器备份表数据