Đếm mảng con có số phần tử khác nhau bằng mảng gốc trong C++

Cho mảng arr[]. Đếm các mảng con mà số phần tử phân biệt trong mảng con bằng số phần tử phân biệt trong mảng gốc. Ví dụ [1,1,2,3] có 3 phần tử phân biệt. Mảng con thỏa mãn: [1,2,3], [1,1,2,3].

Ví dụ

Đầu vào: arr[] = {1,2,1,2,3,4,2}
Đầu ra: 6
Giải thích: Các mảng con có 4 phần tử phân biệt (1,2,3,4).

Đầu vào: arr[] = {8,7,5,6,10}
Đầu ra: 1 (chính mảng gốc).

Giải thuật (Cửa sổ trượt + Hash)

• Dùng unordered_map đếm tần suất phần tử trong cửa sổ.
• Mở rộng cửa sổ bên phải cho đến khi có đủ số phần tử phân biệt bằng mảng gốc.
• Khi đủ, tất cả mảng con mở rộng thêm bên phải cũng thỏa mãn → cộng size - right + 1.
• Thu hẹp cửa sổ bên trái, cập nhật tần suất.

Ví dụ triển khai

#include <bits/stdc++.h>
using namespace std;

int sub_distinct(int arr[], int size) {
    int count = 0, right = 0, left = 0;
    unordered_map<int, int> um;
    for (int i = 0; i < size; ++i) um[arr[i]] = 1;
    int um_size = um.size();
    um.clear();
    for (int i = 0; i < size; ++i) {
        while (right < size && left < um_size) {
            ++um[arr[right]];
            if (um[arr[right]] == 1) ++left;
            ++right;
        }
        if (left == um_size) {
            count += (size - right + 1);
        }
        --um[arr[i]];
        if (um[arr[i]] == 0) --left;
    }
    return count;
}

int main() {
    int arr[] = {4, 3, 2, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Count of subarrays having total distinct elements same as original array are: " << sub_distinct(arr, size);
    return 0;
}

Kết quả

Count of subarrays having total distinct elements same as original array are: 1