[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: posint 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;}
};