259. 3Sum Smaller

[blueWind123731]

Given an array of n integers nums and a 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.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1] [-2, 0, 3] Follow up: Could you solve it in O(n2) runtime?

[blueWind123731]

1.排序从小到大 2.选好第一个数字，在剩下的数字中选取left和right 3.若nums[left]+nums[right]<target-nums[i]，则符合条件，此时left和小于right的数字都满足条件，即加上right-left；否则，right--。

function threeSumSmaller(nums,target){
  if(nums.length<3)return 0
  nums.sort((a,b)=>a-b)
  let count = 0
  const n= nums.length
  for(let i=0;i<n-2;i++){
    let left = i+1
    let right = n-1
    while(left<right){
      if(nums[left]+nums[right]<target-nums[i]){
        count += right-left
        left++
      }else {
        right--
     }
    }
  }
return count
}