Python solution with

  • 0

    Same idea with many other solutions. Was surprised to see no one tries to stop early when the sum of the smallest three numbers already exceeds the target. This little trick makes it beat over 93% of the Python submissions.

    def threeSumSmaller(self, nums, target):
            :type nums: List[int]
            :type target: int
            :rtype: int
            result = 0
            for i in xrange(len(nums)-2):
                j = i+1
                #  break early 
                if nums[i] + nums[j] + nums[j+1] >= target:
                k = len(nums)-1
                while j < k:
                    if nums[i] + nums[j] + nums[k] >= target:
                        k -= 1
                        result += k-j
                        j += 1
            return result

Log in to reply

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