Проблема 3Sum - Leet code - Превышен лимит времени

Question

Я пытаюсь решить проблему 3Sum на Leetcode (https://leetcode.com/problems/3sum/). логика c, которую я использую:

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. Куда я иду не так?

РЕДАКТИРОВАТЬ

Используя ответы, представленные ниже, окончательный лог c, который я построил, будет:

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 из них не пройдены.

Есть ли способ импровизировать время выполнения для этой логики c?

Answer 1

Сортируйте ваш список, чтобы все списки решений были в порядке. Затем добавляйте только тогда, когда новый список отсутствует в наборе решений - ваш текущий тест бесполезен, так как он проверяет скаляры по спискам, что всегда приводит к «Мне нужно это решение».

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]]

Answer 2

Посмотрите на эту строку своего кода

if val not in k or val2 not in k or temp not in k:

Здесь k - списки списков, а val,val2,temp - int. Так что это определенно оценивается как True, и вы всегда добавляете в список.

Также вы должны сначала отсортировать списки перед добавлением в k, чтобы [-1,0,1] и [0,1,-1] были идентифицированы как одинаковые.

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)
                    res = sorted([val,val2,temp])
                    if res not in k:
                        k.append(res)
                        s.update(res)
        return k

Результат:

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