992. Subarrays with K Different Integers

📋 Đề Bài

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] has 3 different integers: 1, 2, and 3.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: 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 = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].

Constraints:

1 <= nums.length <= 2 * 10⁴
1 <= nums[i], k <= nums.length

🧠 Thuật Toán & Kỹ Thuật

Hash Table (Bảng băm)Sliding Window (Cửa sổ trượt)

⏱️ Thời gian O(n)

💾 Không gian O(n)

💻 Lời Giải

C++ 0992-subarrays-with-k-different-integers.cpp

class Solution {
public:
    int sliding_window(vector<int>& nums, int k) {
        int j = 0, n = nums.size();
        int ans = 0;
        unordered_map<int, int> um;
        
        for (int i = 0; i < n; ++i) {
            um[nums[i]]++;
            while (j < n and um.size() > k) {
                um[nums[j]]--;
                if (um[nums[j]] == 0) {
                    um.erase(nums[j]);
                }
                j++;
            }
            ans += i - j + 1;
        }
        
        return ans;
    }
    
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        return sliding_window(nums, k) - sliding_window(nums, k - 1);
    }
};