C++ Sliding Window
See my latest update in repo LeetCode\n## Solution 1. Sliding Window\n\nUse [i, j) as a sliding window to find the maximum window which contains no more than K 
See my latest update in repo [LeetCode](https://github.com/lzl124631x/LeetCode)\n## Solution 1. Sliding Window\n\nUse `[i, j)` as a sliding window to find the maximum window which contains no more than `K` unique elements.\n\nTo achieve this, we use a map `m` to store the last position of each number in the current window.\n\nWhen `m.size() > K`, we should move forward `i` to shrink the window until it become valid again.\n\nWhen `m.size() == K`, `[i, j)` is the maximum window we are looking for. \n\nWithin this maximum window `[i, j)`, there is a minimum window `[k, j)` containing no more than `K` unique elements. `k` is the minimal index in `m`.\n\nNow, the number of valid subarrays in this window is `k - i + 1`.\n\nSince `k` is monotonically increasing and must be no less than `i`, we can use `k` as a global pointer just like `i` and `j` so that the overall time complexity of moving `k` is `O(N)`.\n\nWhenever `m.size() == K`, we can move `k` forward until `m[A[k] - \'0\'] == k`, and add `k - i + 1` to the answer.\n\n```cpp\n// OJ: https://leetcode.com/problems/subarrays-with-k-different-integers/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(N)\nclass Solution {\npublic:\n    int subarraysWithKDistinct(vector<int>& A, int K) {\n        int ans = 0, i = 0, j = 0, k = 0, N = A.size();\n        unordered_map<int, int> m;\n        while (j < N) {\n            m[A[j] - \'0\'] = j;\n            ++j;\n            while (m.size() > K) {\n                int d = A[i++] - \'0\';\n                if (m[d] < i) m.erase(d);\n            }\n            if (m.size() == K) {\n                k = max(i, k);\n                while (m[A[k] - \'0\'] != k) ++k;\n                ans += k - i + 1;\n            }\n        }\n        return ans;\n    }\n};\n```\n\n## Solution 2. Shrinkable Sliding Window\n\nCheck out "[C++ Maximum Sliding Window Cheatsheet Template!](https://leetcode.com/problems/frequency-of-the-most-frequent-element/discuss/1175088/C%2B%2B-Maximum-Sliding-Window-Cheatsheet-Template!)" which can help you solve all sliding window problems.\n\nWe can turn this problem into two find maximum sliding window problem: one is to find a window with at most `k` different integers, another is to find a window with at most `k - 1` different integers.\n\n```cpp\n// OJ: https://leetcode.com/problems/subarrays-with-k-different-integers/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(U) where U is the number of unique numbers in `A`\nclass Solution {\n    int atMost(vector<int> &A, int k) {\n        int distinct = 0, i = 0, j = 0, N = A.size(), ans = 0;\n        unordered_map<int, int> cnt;\n        for (; j < N; ++j) {\n            distinct += ++cnt[A[j]] == 1;\n            while (distinct > k) distinct -= --cnt[A[i++]] == 0;\n            ans += j - i;\n        }\n        return ans;\n    }\npublic:\n    int subarraysWithKDistinct(vector<int>& A, int k) {\n        return atMost(A, k) - atMost(A, k - 1);\n    }\n};\n```
[]