Cho danh sách số nums và số nguyên k. Đếm số dãy con (subarray) chứa chính xác k giá trị khác nhau.
Ví dụ: nums = [2,2,3,4], k=2 → các dãy con: [2,2,3], [2,3], [3,4] → kết quả 3.
Giải thuật (Cửa sổ trượt - Exactly K = AtMost(K) - AtMost(K-1))
- Hàm
count(K)đếm dãy con có ≤ K giá trị khác nhau bằng cửa sổ trượt. - Kết quả =
count(k) - count(k-1).
Mã nguồn Python
from collections import Counter
class Solution:
def solve(self, nums, k):
def count(K):
if K == 0:
return 0
slot = Counter()
i = res = 0
for j, x in enumerate(nums):
slot[x] += 1
while len(slot) > K:
slot[nums[i]] -= 1
if slot[nums[i]] == 0:
del slot[nums[i]]
i += 1
res += j - i + 1
return res
return count(k) - count(k - 1)
ob = Solution()
nums = [2, 2, 3, 4]
k = 2
print(ob.solve(nums, k)) # Output: 3
Đầu vào
[2, 2, 3, 4], 2
Đầu ra
3