Mảng con liên tiếp cân bằng (Contiguous Array) trong C++

Cho mảng nhị phân, tìm độ dài lớn nhất của mảng con liên tiếp có số lượng 0 và 1 bằng nhau.

Ví dụ: [0,1,0] → 2 ([0,1] hoặc [1,0]).

Thuật toán (Prefix Sum + Hash Map)

1. Biến 0 thành -1, 1 giữ nguyên. Tìm mảng con có tổng = 0 dài nhất.
2. Duyệt, tính prefix sum. Lưu chỉ số đầu tiên xuất hiện của mỗi sum vào map.
3. Nếu sum gặp lại tại i, độ dài = i - first_index[sum].

Mã nguồn C++

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

class Solution {
public:
    int findMaxLength(vector& nums) {
        unordered_map mp{{0,-1}};
        int sum=0, ret=0;
        for (int i=0; i v = {0,1,0,0,1};
    Solution ob;
    cout << ob.findMaxLength(v); // 4
    return 0;
}

Đầu vào / Đầu ra

Input: [0,1,0,0,1]

Output: 4