Mảng con lớn nhất có số 0 và 1 bằng nhau C++

Cho mảng chỉ chứa 0 và 1. Tìm mảng con liên tục dài nhất có số lượng 0 = số lượng 1.

Trick: đổi 0 → -1. Khi đó tổng mảng con = 0 ⇔ số 0 = số 1.

Thuật toán Prefix Sum + HashMap (O(N))

• Đổi 0 thành -1.
• Tính prefix sum. Nếu cùng giá trị prefix sum xuất hiện tại 2 chỉ số → đoạn giữa có tổng 0.
• Dùng unordered_map lưu chỉ số đầu tiên của mỗi prefix sum.

Triển khai C++

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

pair longestEqual01(int arr[], int n) {
    unordered_map firstIdx;
    firstIdx[0] = -1; // prefix sum 0 tại chỉ số -1

    int sum = 0, maxLen = 0, endIdx = -1;
    for (int i = 0; i < n; i++) {
        sum += (arr[i] == 0 ? -1 : 1);
        if (firstIdx.count(sum)) {
            int len = i - firstIdx[sum];
            if (len > maxLen) { maxLen = len; endIdx = i; }
        } else {
            firstIdx[sum] = i;
        }
    }
    if (maxLen == 0) return {-1, -1};
    return {endIdx - maxLen + 1, endIdx};
}

int main() {
    int arr[] = {1, 1, 0, 0, 0, 1, 1, 1, 0};
    auto [l, r] = longestEqual01(arr, 9);
    cout << l << ' ' << r << endl; // 1 8
    return 0;
}

Kết quả

1 8