需要优化 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

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

Need Optimized Python Solution for Leetcode 3Sum Question

algorithm

optimization

compare-and-swap

python-3.x