python-3.x - 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 问题，并得到以下代码的 Time Limit Exceeded 错误：

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

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

标签： python-3.xalgorithmoptimizationcompare-and-swap

Answer 1

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