Python solution with hash table O(n^2)


  • 0
    T
    class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            res, n = [], len(nums)
            nums.sort()
            for i in xrange(n):
                if i > 0 and nums[i] == nums[i-1]: continue # avoid duplicates
                target, hashMap, j = 0-nums[i], {}, i+1
                while j < n:
                    if nums[j] in hashMap:
                        res.append([nums[i],nums[hashMap[nums[j]]],nums[j]])
                        while j + 1 < n and nums[j+1] == nums[j]: j += 1 # avoid duplicates
                    hashMap[target-nums[j]] = j
                    j += 1
            return res
    

Log in to reply
 

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