259. 3Sum Smaller

Given an array of n integers nums and an integer target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

Example 1:

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: Because there are two triplets which sums are less than 2:
[-2,0,1]
[-2,0,3]

Example 2:

Input: nums = [], target = 0
Output: 0
Code language: HTTP (http)

Example 3:

Input: nums = [0], target = 0
Output: 0
Code language: HTTP (http)

Constraints:

• n == nums.length
• 0 <= n <= 3500
• 100 <= nums[i] <= 100
• 100 <= target <= 100
• The input is generated such that the answer is less than or equal to 109.

这个题虽然和3sum很像但是有几个明显的不同，一个就是需要找比这个target小的，还有一个是，我们只需要计算有多少组就行了，并不用全部列举出来。

至今为止基本上3sum的题目都是需要先转化成2sum，我们只需要循环原来数列然后 让twoSum的数 小于target- nums[i]

在twoSumSmaller里我们计算有多少对小于target的方法是，把这个数列排序，用两个指针left和right指向最大和最小的数，然后如果两个数的和相加小于target，那么她们之间所有的left 到right之间，以left为其中一个数的数对，都满足条件，所以我们只需要把right-left就可以计算有多少个这样的数对了。

接下来再把left左移，直到循环结束。

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        res= 0
        for i, n in enumerate(nums):
            res += self.twoSmaller(nums[i+1: ], target - n)
        return res

    def twoSmaller(self, nums:List[int], target:int) -> int:
        res = 0
        left = 0
        right = len(nums) -1 
        while left < right:
            if nums[left] + nums[right] < target:
                res += right - left
                left += 1
            else:
                right -= 1

        return res

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        res= 0
        for i, n in enumerate(nums):
            res += self.twoSmaller(nums[i+1: ], target - n)
        return res

    def twoSmaller(self, nums:List[int], target:int) -> int:
        res = 0
        left = 0
        right = len(nums) -1 
        while left < right:
            if nums[left] + nums[right] < target:
                res += right - left
                left += 1
            else:
                right -= 1

        return res