Python beats 98%


  • 8
    class Solution(object):
    def threeSumSmaller(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        nums.sort()
        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
                else:
                    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
    P

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


  • 0
    S

    Hey,

    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.