给你一个包含 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 <= nums.length <= 3000
-105 <= nums[i] <= 105
思路双指针方法:依次对每个元素进行如下判断:-s[i]==s[j]+s[m],其中 s[j]+s[m] 要遍历剩下的元素(采用双指针)
# @lc code=start
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
if set(nums)=={0} and len(nums)>=3:
return [[0,0,0]]
sets=set()
lens=len(nums)
nums =sorted(nums)
result=[]
for i in range(lens):
newlist=nums[0:i]+nums[i+1:]
m=0
j=lens-1-1
if nums[i] in sets:
continue
else:
sets.add(nums[i])
while m<j:
if newlist[m]+newlist[j]==-nums[i] and sorted([newlist[m],newlist[j],nums[i]])not in result:
result.append(sorted([newlist[m],newlist[j],nums[i]]))
m=m+1
elif newlist[m]+newlist[j]>-nums[i]:
j=j-1
else:
m=m+1
return result
# @lc code=end
就差超时了……
方法一:排序 + 双指针
题目中要求找到所有「不重复」且和为 0 的三元组,这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下,数组中的元素全部为 0,即
[0, 0, 0, 0, 0, …, 0, 0, 0]
任意一个三元组的和都为 00。如果我们直接使用三重循环枚举三元组,会得到 O(N^3)个满足题目要求的三元组(其中 N是数组的长度)时间复杂度至少为 O(N^3)。在这之后,我们还需要使用哈希表进行去重操作,得到不包含重复三元组的最终答案,又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高,因此我们要换一种思路来考虑这个问题。
「不重复」的本质是什么?我们保持三重循环的大框架不变,只需要保证:
第二重循环枚举到的元素不小于当前第一重循环枚举到的元素;
第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。
也就是说,我们枚举的三元组 (a, b, c) 满足 a≤b≤c,保证了只有 (a,b,c) 这个顺序会被枚举到,而 (b,a,c)、(c,b,a) 等等这些不会,这样就减少了重复。要实现这一点,我们可以将数组中的元素从小到大进行排序,随后使用普通的三重循环就可以满足上面的要求。
同时,对于每一重循环而言,相邻两次枚举的元素不能相同,否则也会造成重复。举个例子,如果排完序的数组为
[0, 1, 2, 2, 2, 3]
我们使用三重循环枚举到的第一个三元组为 (0, 1, 2),如果第三重循环继续枚举下一个元素,那么仍然是三元组 (0, 1, 2),产生了重复。因此我们需要将第三重循环「跳到」下一个不相同的元素,即数组中的最后一个元素 3,枚举三元组 (0, 1, 3)。
nums.sort()
for first = 0 .. n-1
// 只有和上一次枚举的元素不相同,我们才会进行枚举
if first == 0 or nums[first] != nums[first-1] then
for second = first+1 .. n-1
if second == first+1 or nums[second] != nums[second-1] then
for third = second+1 .. n-1
if third == second+1 or nums[third] != nums[third-1] then
// 判断是否有 a+b+c==0
check(first, second, third)
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
改进:
nums.sort()
for first = 0 .. n-1
if first == 0 or nums[first] != nums[first-1] then
// 第三重循环对应的指针
third = n-1
for second = first+1 .. n-1
if second == first+1 or nums[second] != nums[second-1] then
// 向左移动指针,直到 a+b+c 不大于 0
while nums[first]+nums[second]+nums[third] > 0
third = third-1
// 判断是否有 a+b+c==0
check(first, second, third)
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = list()
# 枚举 a
for first in range(n):
# 需要和上一次枚举的数不相同
if first > 0 and nums[first] == nums[first - 1]:
continue
# c 对应的指针初始指向数组的最右端
third = n - 1
target = -nums[first]
# 枚举 b
for second in range(first + 1, n):
# 需要和上一次枚举的数不相同
if second > first + 1 and nums[second] == nums[second - 1]:
continue
# 需要保证 b 的指针在 c 的指针的左侧
while second < third and nums[second] + nums[third] > target:
third -= 1
# 如果指针重合,随着 b 后续的增加
# 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
if second == third:
break
if nums[second] + nums[third] == target:
ans.append([nums[first], nums[second], nums[third]])
return ans