时间戳

首页 > 解决方案 > 3Sum 问题 - Leet 代码 - 超出时间限制

python - 3Sum 问题 - Leet 代码 - 超出时间限制

问题描述

我正在尝试解决 Leetcode ( https://leetcode.com/problems/3sum/ ) 上的 3Sum 问题。我使用的逻辑是：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        k = list()
        l = len(nums)
        s= set()
        for idx,val in enumerate(nums):
            for j in range(idx+1,l):
                val2 = nums[j]
                temp = 0 - (val + val2)
                if temp in nums[j+1:]:
                    print(s)
                    if val not in k or val2 not in k or temp not in k:
                        k.append([val,val2,temp])
                        s.update([val,val2,temp])
        return k

为了不在结果中添加重复列表（具有相同元素的列表），我将所有唯一值推送到一个集合中。然后在添加到列表之前检查该集合是否至少不包含三个元素之一。我认为这应该可以防止我添加重复的列表。如果我错了，请纠正我。

但我看到的输出结果是：

Your input
    [-1,0,1,2,-1,-4]
stdout
    set()
    {0, 1, -1}
    {0, 1, 2, -1}
Output
    [[-1,0,1],[-1,2,-1],[0,1,-1]]
Expected
    [[-1,-1,2],[-1,0,1]]

[0,1,-1]即使集合s包含所有三个元素，我也不明白为什么要添加到我的结果中0,1,-1。我哪里错了？

编辑

使用下面发布的答案，我构建的最终逻辑是：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        k = list()
        l = len(nums)
        for idx,val in enumerate(nums):
            for j in range(idx+1,l):
                val2 = nums[j]
                temp = 0 - (val + val2)
                if temp in nums[j+1:]:
                    item = sorted([val,val2,temp])
                    if item not in k:
                        k.append(item)
        return k

但是，当我运行它时，大量输入超出了时间限制。我收到错误消息Time Limit Exceeded。311/313 个测试用例通过，其中 2 个失败。

有没有办法即兴发挥这个逻辑的运行时间？

标签： pythonlogic

解决方案

对您的列表进行排序，以便所有解决方案列表都按顺序排列。然后仅在新列表不在解决方案集中时添加 - 您当前的测试是无用的，因为它会根据列表检查标量，这将始终导致“我需要这个解决方案”。

nums = [-1,0,1,2,-1,-4]
nums.sort()
print(nums)
k = list()
l = len(nums)
s= set()
old_val2 = None
for idx, val in enumerate(nums):
    for j in range(idx+1,l):
        val2 = nums[j] 
        temp = 0 - (val + val2)
        if temp in nums[j+1:]:
            print(s)
            # if val not in k or val2 not in k or temp not in k:
            if [val, val2, temp] not in k:
                k.append([val,val2,temp])
                s.update([val,val2,temp])
print(k)

输出：

[-4, -1, -1, 0, 1, 2]
set()
{2, -1}
{0, 1, 2, -1}
[[-1, -1, 2], [-1, 0, 1]]

推荐阅读