Saved from https://leetcode.com/problems/3sum-smaller/submissions/

lc259

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        """
        If we fix one dimension, the question essentially becomes a "two sum smaller" problem
        The ideas are:
        1) when sum < target, count += r - l, then we need to move left to the next bigger value
        2) otherwise move r to the next smaller value
        """
        nums.sort()
        n = len(nums)
        count = 0
        for start in range(n-2):
            l, r = start + 1, n - 1
            while l < r:
                curr_sum = nums[start] + nums[l] + nums[r]  
                if curr_sum < target:
                    count += r - l
                    l += 1
                else:
                    r -= 1
                    
        return count