随心情不定时更新,什么都可能写一点的技术博客

0%

三数之和

问题

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。LeetCode原题入口

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]


思路

如果简单采用暴力遍历的方式,时间复杂度为$ O(n^3) $,时间上肯定无法通过。可先对数组进行排序,时间复杂度为$ O(n\log n) $,接着从数组第一个数开始遍历,在剩下的数中取2数之和,正好等于第一个数的相反数,这样3者之和正好为0。

设置第一个指针遍历数组,假设遍历到的当前数为x,则要找的2数之和target=-x,由于数组已经经过排序,后面2数可再用2个指针表示,1个指向第1个数的后一个数,也就是正好大于x的数,另1个指向数组最后一位,也就是最大的那个数。计算2个指针所指向数字之和,如果结果大于target,说明结果偏大,将第2个指针向左移动;如果结果小于target,将第1个指针向右移动,使结果偏大;如果相等,说明符合条件,将数字收纳到结果集里面。
最后,由于题目不允许重复,这3个指针如果移动过程中,碰到和上一个数字一样,则直接跳过,时间复杂度为$ O(n^2) $。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def threeSum(self, nums: List[int]) -> List[List[int]]:
res=[]
nums=sorted(nums)
for i in range(len(nums)):
if i>0 and nums[i]==nums[i-1]:
continue
target=-nums[i]
j,k=i+1,len(nums)-1
while j<k:
if nums[j]+nums[k]>target:
k-=1
elif nums[j]+nums[k]<target:
j+=1
else:
if nums[j]+nums[k]==target:
res.append([nums[i],nums[j],nums[k]])
j+=1
k-=1
while j<k and nums[j]==nums[j-1]:
j+=1
while j<k and nums[k]==nums[k+1]:
k-=1
return res