Contiguous Array หาสับอาร์เรย์ติดกันที่มี 0 และ 1 เท่ากันใน C++

ให้อาร์เรย์ไบนารี หาความยาวสูงสุดของ subarray ติดกันที่มีจำนวน 0 และ 1 เท่ากัน

ตัวอย่าง: [0,1,0] → 2 (subarray [0,1] หรือ [1,0])

วิธีแก้ปัญหา (Prefix Sum + Hash Map)

แปลง 0 → -1, 1 → +1 หา subarray ที่ผลรวม = 0 (ยาวที่สุด)

1. ret = 0, sum = 0, map m เก็บ {sum: index}
2. m[0] = -1
3. วน i = 0 ถึง n-1:
   • sum += (nums[i] == 1 ? 1 : -1)
   • ถ้า sum อยู่ใน m: ret = max(ret, i - m[sum])
   • มิฉะนั้น: m[sum] = i
4. คืนค่า ret

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int ret = 0;
        int sum = 0;
        map<int, int> m;
        m[0] = -1;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i] == 1 ? 1 : -1;
            if (m.count(sum)) ret = max(ret, i - m[sum]);
            else m[sum] = i;
        }
        return ret;
    }
};

int main() {
    vector<int> v = {0,1,0,0,1};
    Solution ob;
    cout << ob.findMaxLength(v);
    return 0;
}

Input

[0,1,0,0,1]

Output

4