Leetcode 15.三数之和题解
程序员文章站
2022-07-14 17:34:09
...
Leetcode 15.三数之和题解
题目链接:
https://leetcode-cn.com/problems/3sum/
题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
思路
看到这道题我的第一反应就是暴力解,遍历三遍数组求解,这样做显然是O(n3)的时间复杂度。于是我就开始想有没有更快的解法,很容易就可以想到先固定一个数,然后去求数组中和为这个数负数的另两个数。咦,仔细一看那这不就是leetcode第一题嘛。只要做过应该就知道可以拿hash来求解,那直接把这个方法套过来可以吗?答案显然是可以的。不过还需要注意的是答案中不包含重复三元组,所以最好先对数组排个序。那么这个方法的时间复杂度就是O(2),空间复杂度就是O(n)。
u1s1,我的思路到这里就停止了,但看了一眼答案,发现用双指针的方法可以做到空间复杂度只有O(1)。我觉得很强,所以也在这里分享一下。双指针法有一个前提是数组需要有序,这是因为有序数组才可以决定两个指针的移动顺序和方向。假设我们是一个升序排列的数组,如下图,我们先遍历我们的数组,固定三元组的其中一位(就好比图中的3),然后设定两个指针分别是其下一位和数组末尾(图中红色箭头)。
当两个指针对应的数求和结果大于固定元的负数时,那么向左移动右侧指针,如果小于,则向右移动左侧指针,如果相等,那么便是其中一个答案,并同时向内侧移动两个指针。
代码
hash法
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res = []
num_dict = {}
for n in nums:
if n in num_dict:
num_dict[n] += 1
else:
num_dict[n] = 1
for i, n in enumerate(nums):
if i > 0 and nums[i-1] == n:
continue
for j in range(i+1, len(nums)):
if j > i+1 and nums[j-1] == nums[j]:
continue
if -nums[j]-n not in num_dict:
continue
if -nums[j]-n < nums[j]:
continue
if -nums[j]-n > nums[j]:
res.append([n, nums[j], -nums[j]-n])
else:
tmp = 2 if n != nums[j] else 3
if num_dict[-nums[j]-n] >= tmp:
res.append([n, nums[j], -nums[j]-n])
return res
双指针法
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
res = []
for i, n in enumerate(nums):
start, end = i+1, len(nums) - 1
if i > 0 and nums[i-1] == n:
continue
while start < end:
if nums[start] + nums[end] < -n:
start += 1
elif nums[start] + nums[end] > -n:
end -= 1
else:
res.append([n, nums[start], nums[end]])
start += 1
end -= 1
while start > i+1 and start < end and nums[start] == nums[start-1]:
start += 1
while end < len(nums)-1 and end > start and nums[end] == nums[end+1]:
end -= 1
return res