Improved 2-pointer solution for python


  • 0
    E

    This one uses the same way like other posts to avoid duplicates, but beats 99% of python submissions. The idea is to skip some iterations when the sum is obviously positive.
    Here are the details (assume i<j<k):
    (1) a[i] >0, stop iteration.
    (2) For every j, record the smallest k in the list kref. This value is used as the max limit for k of iteration i+1, since sum(i+1, j, k) > sum(i, j, k) > 0.

            if len(nums) < 3:
                return []
            nums = sorted(nums)
            kref = [len(nums)-1 for _ in nums]
            out = []
            i = 0
            while nums[i] <= 0 and i < len(nums)-2:
                if i > 0 and nums[i] == nums[i-1]:
                    i += 1
                    continue
                j = i+1
                k = kref[j]
                while j < k:
                    s = nums[i]+nums[j]+nums[k]
                    if s < 0:
                        j += 1
                    elif s > 0:
                        k -= 1
                        kref[j] = k
                    else:
                        out.append([nums[i], nums[j], nums[k]])
                        while j < k and nums[j] == nums[j+1]:
                            j += 1
                        while j < k and nums[k] == nums[k-1]:
                            k -= 1
                        j += 1
                        k -= 1
                i += 1
            return out
    

Log in to reply
 

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