นับ Subarray ที่มีจำนวน A และ B เท่ากันใน C++

เราได้รับอาร์เรย์ arr[] และตัวเลข A, B เป้าหมายคือนับ subarray ที่จำนวนครั้งที่ A และ B ปรากฏเท่ากัน

ตัวอย่าง

อินพุต: arr[] = {2, 2, 1, 1, 1, 5}, A=1, B=5

เอาต์พุต: 4

คำอธิบาย: [2], [2], [2,2] (ไม่มี 1 และ 5), [1,5] (มี 1 และ 5 ครั้งละ 1)

อินพุต: arr[] = {5, 3, 7, 5, 3}, A=1, B=2

เอาต์พุต: 15

คำอธิบาย: ทุก subarray ไม่มี 1 และ 2 เลย (0 occurrences ทั้งคู่) รวม 15 subarray

แนวทางการแก้ปัญหา (Naive O(n²))

ใช้ nested loop สร้าง subarray ทุกคู่ นับ A และ B ในแต่ละ subarray ถ้าเท่ากันนับเพิ่ม

การนำไปใช้ (Implementation)

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

int sub_EqualOccurrence(int arr[], int size, int A, int B) {
    int count = 0;
    for (int i = 0; i <= size - 1; i++) {
        int total_A = 0, total_B = 0;
        for (int j = i; j <= size - 1; j++) {
            if (arr[j] == A) total_A++;
            else if (arr[j] == B) total_B++;
            if (total_A == total_B) count++;
        }
    }
    return count;
}

int main() {
    int arr[] = {2, 3, 1, 1, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int A = 1, B = 5;
    cout << "Count of subarrays with equal number of occurrences of two given elements are: " << sub_EqualOccurrence(arr, size, A, B);
    return 0;
}

เอาต์พุต

Count of subarrays with equal number of occurrences of two given elements are: 5

หมายเหตุ: สามารถปรับปรุงเป็น O(n) ได้โดยใช้ prefix difference และ hash map