Đếm cặp từ các mảng con phần tử phân biệt trong C++

Cho một mảng arr[] chứa các phần tử nguyên. Mục tiêu là tìm số cặp có thể tạo thành từ các phần tử của mảng con của arr[] sao cho mỗi mảng con chỉ chứa các phần tử phân biệt. Nếu mảng là [1,2,2,3,3] thì mảng con phân biệt là [1,2] và [2,3]. Cặp là (1,2) và (2,3) -> count = 2.

Ví dụ

Đầu vào - arr[] = {1,2,5,3}

Đầu ra - Số cặp từ mảng con phân biệt là 6

Giải thích - Mảng con phân biệt: [1,2,5,3], cặp: (1,2), (1,3), (1,5), (2,5), (2,3), (5,3) = 6 cặp.

Đầu vào - arr[] = {1,2,1,2,3}

Đầu ra - Số cặp từ mảng con phân biệt là 5

Giải thích - Mảng con phân biệt: [1,2] - cặp: (1,2) [2,1] - cặp: (2,1) [1,2,3] - cặp: (1,2), (2,3), (1,3) Tổng: 5 cặp

Phương pháp sử dụng

• Nhập mảng nguyên
• Hàm distinct_pairs(int arr[], int size) trả về số cặp
• Khởi tạo count = 0, start = end = 0
• Vector check(size, false) đánh dấu phần tử trong cửa sổ
• Vòng lặp WHILE start < size
• Trong đó: WHILE start < size VÀ !check[arr[start]]: count += start - end; check[arr[start]] = true; start++
• WHILE end < start VÀ start != size VÀ check[arr[start]]: check[arr[end]] = false; end++
• Trả về count

Chương trình minh họa

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

int distinct_pairs(int arr[], int size) {
    int count = 0;
    int start = 0;
    int end = 0;
    vector<bool> check(size, false);
    
    while (start < size) {
        while (start < size && !check[arr[start]]) {
            count += (start - end);
            check[arr[start]] = true;
            start++;
        }
        while (end < start && (start != size && check[arr[start]])) {
            check[arr[end]] = false;
            end++;
        }
    }
    return count;
}

int main() {
    int arr[] = {5, 1, 8, 2, 1, 7, 9, 1};
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Số cặp từ mảng con phần tử phân biệt là: " << distinct_pairs(arr, size);
    return 0;
}

Đầu ra

Số cặp từ mảng con phần tử phân biệt là: 17