Why my code TLE? Python, O(n^2)


  • 0
    H
    class Solution:
        # @return a list of lists of length 3, [[val1,val2,val3]]
        def threeSum(self, num):
            array=[]
            if len(num)<3:
                return array
            num=sorted(num)
            for i in xrange(len(num)):
                for j in xrange(i+1,len(num)):
                    if -(num[i]+num[j]) in num and sorted([num[i],num[j],-(num[i]+num[j])]) not in array and num.index(-(num[i]+num[j]))!=i and num.index(-(num[i]+num[j]))!=j:
                        array.append(sorted([num[i],num[j],-(num[i]+num[j])]))
            return array

  • 0
    V

    num in your code is a list. So the -(num[i] + num[j]) in num will take O(n) time to find whether the element is in the list. So the total time complexity of your code is O(n^3).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.