Оптимизация времени выполнения решения до проблемы 3Sum - PullRequest
Новая
       12

Оптимизация времени выполнения решения до проблемы 3Sum

0 голосов
/ 21 февраля 2020

Я пытаюсь найти все уникальные триплеты в данном наборе целых чисел, сумма которых равна нулю. У меня есть следующий код, который работает для меня логически, но я получаю ошибку тайм-аута. Любой совет о том, что мне не хватает или как оптимизировать? Я прошел через это несколько раз, и я не вижу, как сделать это быстрее. Заранее спасибо! 

class Solution:
def threeSum(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    nums.sort()
    for i in range(len(nums)-2):
        if i > 0 and nums[i] == nums[i-1]:
            continue

        target = 0 - nums[i]
        j = i +1
        k = len(nums) - 1
        tgt_sum = 0
        trpls = []

        while j < k:
            tgt_sum = nums[j] + nums[k]
            if tgt_sum == target:
                x = []
                x.append([i,j,k])
                if all(item in trpls for item in x) == True:
                    trpls_list.append([i,j,k])
            elif tgt_sum < target:
                j += 1
            elif tgt_sum > target:
                k -= 1
            else:
                k -= 1

test = Solution()
given_nums = [-1,0,1,2,-1,-4]
print(test.threeSum(given_nums))
...