Fast python solution 160ms


  • 0
    P

    The algorithm is straightforward: use a map to record the value count and generate triplets with at least two identical elements. Then the list is de-duped and sorted so the normal two-pointer approach would apply. Running time is 160 ms.

    class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            M = {}
            for v in nums:
                M[v] = M.get(v,0) + 1
            results = []
            for v in M.keys():
                if v == 0:
                    if M[0] >= 3:
                        results.append([0,0,0])
                else:
                    if M[v] >= 2 and -(v<<1) in M:
                        if v > 0:
                            results.append([-(v<<1),v,v])
                        else:
                            results.append([v,v,-(v<<1)])
            nums = M.keys()
            nums.sort()
            N = len(nums)
            for i in range(N-2):
                start,end = i+1,N-1
                while start < end:
                    if nums[start]+nums[end]+nums[i] < 0:
                        start += 1
                    elif nums[start]+nums[end]+nums[i] > 0:
                        end -= 1
                    else:
                        results.append([nums[i],nums[start],nums[end]])
                        start += 1
                        end -= 1
            return results

  • 0
    L

    It's a little bit tedious, you have to take care of many details and you wouldn't have enough time to finish all these if it's real question in interview.


  • 0
    B

    Can you explain some of your optimizations? I am confused; why exclude starting and ending elements?


Log in to reply
 

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