Python O(n^2) TLE why?


  • 1
    H
    class Solution:
        # @param {integer[]} nums
        # @return {integer[][]}
        def threeSum(self, nums):
            n = len(nums)
            h = {}
            rlt = []
            for i in range(n):
                h[nums[i]] = i
            for i in range(n):
                for j in range(n):
                    if i != j:
                        x = -(nums[i]+nums[j])
                        if x in h and h[x] != i and h[x] != j:
                            t = tuple(sorted([nums[i],nums[j],x]))
                            if t not in rlt: rlt.append(t)   
            return rlt

  • 0
    C

    The reason I think is that you didnot avoid duplicates in your process, yes, the result of your code maybe is correct, and the time complexity is O(n*n) the same as others, but the OJ for this question is a little bit strict, such as if the list is -1, 0, 0, 1, 1, 1, 1, 1, 1, after you checking the first 1, you can move the index forward without checking the sum, because they are duplicates. Here is a method to avoid duplicates, just for reference.

    def threeSum(self, nums):
        nums.sort()
        res, leng = [], len(nums)
        for i in xrange(leng-2):
            if i == 0 or nums[i] != nums[i-1]:
                l, r = i+1, leng-1
                while l < r:
                    s = nums[i] + nums[l] + nums[r]
                    if s == 0:
                        res.append((nums[i], nums[l], nums[r]))
                        while l < r and nums[l] == nums[l+1]:
                            l += 1
                        while r > l and nums[r] == nums[r-1]:
                            r -= 1
                        l += 1; r -= 1
                    elif s > 0:
                        r -= 1
                    else:
                        l += 1
        return res

  • 0
    L

    Truly it is really confusing when the OJ says TLE, but it is actually the failure to avoid duplicate. People's attention can be distracted to other trivial programming details to save time, while the answer itself is wrong.


Log in to reply
 

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