<div>
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:
<pre>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] </pre>
Example 2:
<pre>Input: nums = [], target = 0 Output: 0 </pre>
Example 3:
<pre>Input: nums = [0], target = 0 Output: 0 </pre>
Constraints:
n == nums.length0 <= n <= 3500-100 <= nums[i] <= 100-100 <= target <= 100
</div>
题目大意：
找三数和小于target的组合个数
解题思路：
类似于三数和等于target，但当小于target时，直接求个数，类似于LeetCode 315 Count of Smaller Numbers After Self。
解题步骤：
N/A
注意事项：
- res不是+1而是right - left
Python代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14def threeSumSmaller(self, nums: List[int], target: int) -> int:
if len(nums) < 3:
return 0
nums.sort()
res = 0
for i in range(len(nums) - 2):
left, right = i + 1, len(nums) - 1
while left < right:
if nums[i] + nums[left] + nums[right] < target:
res += right - left # remember
left += 1
else:
right -= 1
return res
算法分析：
时间复杂度为<code>O(n<sup>2</sup>)</code>，空间复杂度O(1)
