<p>Given an integer array <code>nums</code> and an integer <code>k</code>, return <em>the number of <strong>good subarrays</strong> of </em><code>nums</code>.</p>

<p>A <strong>good array</strong> is an array where the number of different integers in that array is exactly <code>k</code>.</p>

<ul>
	<li>For example, <code>[1,2,3,1,2]</code> has <code>3</code> different integers: <code>1</code>, <code>2</code>, and <code>3</code>.</li>
</ul>

<p>A <strong>subarray</strong> is a <strong>contiguous</strong> part of an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,1,2,3], k = 2
<strong>Output:</strong> 7
<strong>Explanation:</strong> 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]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,1,3,4], k = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= nums[i], k &lt;= nums.length</code></li>
</ul>

class Solution {
public:
    vector <int> nums;
    int subproblem(int k) {
        // mô tả bài toán con: là số mảng con liên tiếp có số phần tử khác nhau <= k
        // với mỗi phần tử slow bên trái, ta sẽ dịch fast bên phải sao cho fast lớn nhất có thể và
        // số phần tử khác nhau giữa slow và fast <= k

        // unordered_map để lưu trữ frequency
        unordered_map <int, int> frequency;
        int countDistinct = 0;
        int fast = 0;
        int res = 0;
        for (int slow = 0; slow < nums.size(); slow++) {
            // ta luôn cần duy trì fast là biến xa nhất so với slow thỏa mãn
            while (fast < nums.size()) {
                if (countDistinct == k && (frequency.count(nums[fast]) == 0 || frequency[nums[fast]] == 0)) {
                    break;
                }

                if (frequency.count(nums[fast]) == 0) {
                    frequency[nums[fast]] = 0;
                }
                frequency[nums[fast]]++;
                if (frequency[nums[fast]] == 1) {
                    countDistinct++;
                }

                fast++;
            }

            res += (fast - slow);

            // cout << slow << " " << fast << " " << res << "\n";

            frequency[nums[slow]]--;
            if (frequency[nums[slow]] == 0) {
                countDistinct--;
            }
        }
        // cout << "\n";
        return res;
    }
    int subarraysWithKDistinct(vector<int>& nums, int k) {
        // expected complexity (from constraints): O(n sqrt(n)), O(n), O(n log(n)), ...
        // Brute forces -> cải tiến

        // for từng điểm xuất phát. Ta nhận thấy khi đi qua mỗi phần tử tiếp theo, số phần tử lớn dần,
        // và số phần tử khác nhau sẽ tăng dần.
        // Vì vậy, kết quả của [l, r + 1] có thể được lợi dùng từ [l, r] -> O(n^2)

        // unordered_set <int> shown;
        // int res = 0;
        // int n = nums.size();
        // for (int i = 0; i < n; i++) {
        //     shown = {};
        //     for (int j = i; j < n; j++) {
        //         if (shown.size() > k) {
        //             break;
        //         }
        //         shown.insert(nums[j]);
        //         if (shown.size() == k) {
        //             res++;
        //         }
        //     }
        // }
        // return res;

        // Các pp cải tiến cho thuật toán này:
        // Approach: giữ cách để di chuyển con trỏ i từ trái qua phải
        // Con trỏ j sẽ phải làm nhiệm vụ đứng ở vị trí nào đó xa i nhất mà từ i đến j có đúng k phần tử khác nhau
        // nums[i, j] có k phần tử khác nhau, nums[i, j + 1] sẽ là k + 1 phần tử khác nhau.

        // Ta sẽ đếm xem với mỗi i, có bao nhiêu mảng con mà có ít hơn k + 1 phần tử khác nhau. Đặt là f(i, k + 1)
        // kết quả sẽ là f(i, k + 1) - f(i, k)
        // Ta định nghĩa subproblem(k) là số mảng con liên tiếp có số phần tử khác nhau <= k
        this->nums = nums;
        return subproblem(k) - subproblem(k - 1);
    }
};
54661