動機
sliding window的新招式
- binary search的range是左閉右開
- lower bound:
>=的第一個值
- upper bound:
>的第一個值
- lower bound:
- sliding window是左閉右閉
- atMost:
<=目標的所有區間總數
- atMost:
Problem
Given an integer array nums
and an integer k
, return the number of good subarrays of nums
.
A good array is an array where the number of different integers in that array is exactly k
.
- For example,
[1,2,3,1,2]
has3
different integers:1
,2
, and3
.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,2,1,2,3], k = 2Output: 7Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
Example 2:
Input: nums = [1,2,1,3,4], k = 3Output: 3Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
Constraints:
1 <= nums.length <= 2 * 104
1 <= nums[i], k <= nums.length
Sol
class Solution:
def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
def atmost(bound):
ret = i = 0
cnts = defaultdict(int)
for j,n in enumerate(nums):
cnts[n] += 1
while i <= j and len(cnts) > bound:
if cnts[nums[i]] == 1:
del cnts[nums[i]]
else:
cnts[nums[i]] -= 1
i += 1
ret += j-i+1
return ret
return atmost(k)-atmost(k-1)