Mảng con với K số nguyên khác nhau trong C++

Cho mảng A các số nguyên dương. Mảng con "tốt" là mảng con liên tiếp có đúng K số nguyên khác nhau. Tìm số lượng mảng con tốt.

Ví dụ: A=[1,2,3,1,4], K=3 → 4 mảng con: [1,2,3], [1,2,3,1], [2,3,1], [3,1,4].

Giải thuật

1. Sử dụng kỹ thuật cửa sổ trượt: số mảng con có đúng K giá trị khác nhau = atMost(K) - atMost(K-1).
2. Hàm atMost(a, k): đếm mảng con có ≤ k giá trị khác nhau.
   • Duyệt i (phải), mở rộng cửa sổ. Dùng map m đếm tần suất.
   • Khi thêm a[i] làm tăng số giá trị khác nhau > k, thu hẹp cửa sổ từ trái (j++) cho đến khi thỏa mãn.
   • Mỗi bước, số mảng con kết thúc tại i là (i-j+1), cộng vào ans.
3. Trả về atMost(K) - atMost(K-1).

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int subarraysWithKDistinct(vector<int>& a, int k) {
        return atMost(a, k) - atMost(a, k - 1);
    }
    int atMost(vector<int>& a, int k){
        int j = 0, ans = 0;
        unordered_map<int, int> m;
        for(int i = 0; i < a.size(); i++){
            if(!m[a[i]]++) k--;
            while(k < 0){
                if(!--m[a[j]]) k++;
                j++;
            }
            ans += (i - j + 1);
        }
        return ans;
    }
};
int main(){
    Solution ob;
    vector<int> v = {1,2,3,1,4};
    cout << (ob.subarraysWithKDistinct(v, 3));
}

Đầu vào

{1,2,3,1,4}, 3

Đầu ra

4