LeetCode 259 3Sum Smaller

LeetCode

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

Example 3:

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

Constraints:

n == nums.length 0 <= n <= 3500
-100 <= nums[i] <= 100 -100 <= target <= 100

题目大意：

找三数和小于target的组合个数

解题思路：

类似于三数和等于target，但当小于target时，直接求个数，类似于LeetCode 315 Count of Smaller Numbers After Self。

解题步骤：

N/A

注意事项：

1. res不是+1而是right - left

Python代码：

def 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

算法分析：

时间复杂度为O(n2)，空间复杂度O(1)