需要针对Leetcode 3Sum问题的优化Python解决方案

Question

这是问题陈述：

Given an array nums of n integers, 
are there elements a, b, c in nums such  that a + b + c = 0? 
Find all unique triplets in the array which gives the sum of zero.

注意：

解决方案集不得包含重复的三元组。

例：

Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[[-1, 0, 1],[-1, -1, 2]]

我现在正在解决 Leetcode 3Sum 问题，并收到以下代码的"超出时间限制"错误：

class Solution:
def threeSum(self, nums):
triplets=[]
nums.sort()
for i in range(len(nums)-1):
l=i+1
r=len(nums)-1
while l<r:
sum=nums[i]+nums[l]+nums[r]
if sum==0:
if not [nums[i],nums[l],nums[r]] in triplets:
triplets+=[[nums[i],nums[l],nums[r]]]
if sum<0:
l+=1
else:
r-=1
return triplets

谁能告诉我在哪里可以优化此代码？

Answer 1

您的算法总体上看起来是最佳的(存在稍微好一点的复杂性，但对于实际目的来说，方法可能太复杂了(。

但似乎在列表中搜索子列表的操作相当缓慢(对于未排序可能是线性的(

改用字典并在末尾提取三元组。

Answer 2

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
N = len(nums)
for i in range(N):
if i > 0 and nums[i] == nums[i-1]:
continue
target = -nums[i]
l = i + 1
r = N - 1
while l < r:
if nums[l] + nums[r] == target:
result.append([nums[l],nums[r],nums[i]])
l = l + 1
while l <= r and nums[l] == nums[l - 1]:
l = l + 1
elif nums[l] + nums[r] > target:
r = r - 1
else:
l = l + 1
return result