Python beats 98%

  • 9
    class Solution(object):
    def threeSumSmaller(self, nums, target):
        :type nums: List[int]
        :type target: int
        :rtype: int
        res = 0
        for i in xrange(0, len(nums) - 2):
            if 3*nums[i] >= target:
                return res
            start = i + 1
            end = len(nums) - 1
            while start < end:
                # print nums[i], nums[start], nums[end]
                if nums[i] + nums[start] + nums[end] < target:
                    res += end - start
                    start += 1
                    end -= 1
        return res

    Since the array is sorted, the lower bound of 3sum will be 3*nums[i]. If 3*nums[i] is not less than target, then the rest of them cannot meet the requirement too.

  • 0

    oh man this is so concise the brilliant! thanks for sharing!

  • 0


    Please forgive my stupid question but can somebody help understand what does this line count

    res += (end-start)

    how does it count pairs of numbers adding with nums[i] to form a sum < target

Log in to reply

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