Нужно оптимизированное решение Python для Leetcode 3Sum Вопрос - PullRequest
Новая
       35

Нужно оптимизированное решение Python для Leetcode 3Sum Вопрос

0 голосов
/ 24 октября 2018

Вот формулировка проблемы: 

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

Может кто-нибудь сказать мне, где я могу оптимизировать этот код?

1 Ответ

0 голосов
/ 24 октября 2018

Ваш алгоритм выглядит оптимальным в целом (немного лучшая сложность существует, но подход, возможно, слишком сложен для практических целей).

Но кажется, что поиск подсписка в списке довольно медленная операция (возможно, линейная для несортированных)

Используйте словарь и извлекайте тройки в конце.

...