[LeetCode] Contiguous Array | 转化为找和为0的最长子段

https://leetcode.com/problems/contiguous-array/?tab=Solutions

先把所有的0变成-1，问题就变成找最长的和为0的子段（设长度为ret，初始化为0）。然后扫描一次数组，计算前缀和并存入一个哈希表，每计算一个位置i的前缀和prefix_sum，

1. 判断是否等于0，等于0的话，ret = max(ret, i + 1)
2. 否则在哈希表里找是否存过和为prefix_sum的下标，有的话，ret = max(ret, i - hash_map[prefix_sum])

Time complexity: O(n)
Space complexity: O(n)

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        if (nums.empty()) return 0;
        
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] == 0) nums[i] = -1;
        }
        
        unordered_map<int, int> hash_table;  // key: prefix sum, value: pos
        int prefix_sum = 0, ret = 0;
        for (int i = 0; i < nums.size(); ++i) {
            prefix_sum += nums[i];
            if (prefix_sum == 0) {
                ret = max(ret, i + 1);
                continue;
            }
            if (hash_table.find(prefix_sum) == hash_table.end()) {
                hash_table[prefix_sum] = i;
            } else {
                ret = max(ret, i - hash_table[prefix_sum]);
            }
        }
        
        return ret;
    }
};