• ㊗️
• 大家
• offer
• 多多！

## Problem

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.

Follow up: Could you solve it in O(n2) runtime?

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


Example 3:

Input: nums = [0], target = 0
Output: 0


## Code

class Solution {
public int threeSumSmaller(int[] nums, int target) {
int res = 0;
Arrays.sort(nums);

for(int i = 0; i < nums.length; i++){
int left = i + 1;
int right = nums.length - 1;
while(left < right){
if(nums[i] + nums[left] + nums[right] < target){
// 因为已经是排序过的，所以如果nums[left] + nums[right]的值都小于target
// 那nums[left] + nums[right - 1]也一定小于target
// 所以可以让res直接加上这段index的差值
// 0，1，2，3，4，5
//    l         r
// 结果就是r - l = 4
// 对应[1,5],[1,4],[1,3],[1,2]这四个结果
res += right - left;
left++;
} else {
right--;
}
}
}

return res;
}
}

class Solution:
def threeSumSmaller(self, nums: List[int], target: int) -> int:
if not nums or len(nums) < 3:
return 0

nums.sort()

res = 0
for i in range(0, len(nums) - 2, 1):
num1 = nums[i]
left = i + 1
right = len(nums) - 1

while left < right:
sum = num1 + nums[left] + nums[right]
if sum < target:
res += right - left
left += 1
else:
right -= 1

return res