196ms Python Solution with explanation


  • 1
    H
    class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            ret=[]
            nums=sorted(nums)
            n=len(nums)
            if n==0:
                return ret
            i=0
            while i<n:
                l,r=i+1,n-1
                target=-nums[i]
                while l<r:
                    if nums[l]+nums[r]==target:
                        ret.append([nums[i],nums[l],nums[r]])
                        lc,rc=l,r
                        l+=1
                        r-=1
                        # move ahead to avoid duplicates
                        while l<=r and nums[lc]==nums[l]:
                            l+=1
                        while r>=l and nums[rc]==nums[r]:
                            r-=1
                    elif nums[l]+nums[r] < target:
                        l+=1
                    else:
                        r-=1
                j=i+1
               # move ahead to avoid duplicates
               while j<n and nums[j]==nums[i]:
                    j+=1
                i=j
            return ret
    

    The idea is from this post. We can follow two pointer approach in a sorted array to find the pairs of elements in the array that sum up to a given value. So, we first sort the array and for each element (a[i]) in the array we search for a pair which sums up to (-a[i]) on the right of a[i]. This way we can find triplets that sum up to 0. The edge case is that there should be no duplicates, so we move ahead if we see repeated elements.


Log in to reply
 

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