Correct answer. But why O(N2) gives Time limit Exceeded?


  • 1
    L
    class Solution:
        # @return a list of lists of length 3, [[val1,val2,val3]]
        def threeSum(self, num):
            if not num:
                return []
            hash_table = {}
            for i in range(len(num)):
                if num[i] not in hash_table:
                    hash_table[num[i]] = 1
                else:
                    hash_table[num[i]] += 1
            res = []
            for i in range(len(num)):
                for j in range(i+1,len(num)):
                    hash_table[num[i]] -= 1
                    hash_table[num[j]] -= 1
                    wanted = -num[i]-num[j]
                    if wanted in hash_table and hash_table[wanted] > 0:
                        new = [num[i],num[j], wanted]
                        new.sort()
                        if new not in res:
                            res.append(new)
                    hash_table[num[i]] += 1
                    hash_table[num[j]] += 1
            return res

  • 0
    K

    me too. Triggered a time limit error despite being a O(n^2) algorithm


  • 0
    L

    'if new not in res' could run quite a long time
    and could use collections.Counter() as hash_table


Log in to reply
 

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