LC525.连续数组

方法：前缀和 + 哈希表优化

1. 需要处理掉原有的0，将其转化成-1，因为0不产生变化，假如有多个连续的0，根本不清楚到底有多少个，转化成-1是方便处理的。
2. 利用前缀和建立数组，将问题转化成：在前缀和序列中，如果出现两个相同的数，那么两数的距离最大是多少？
3. 利用哈希表去解决找到最大距离的问题，如果数字已经在表项中了，那么去计算距离即可，如果数字不在表项中，那么更新表项（这样就不存在后面覆盖前面的问题了）
   具体代码如下:

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        /* 
            前缀和 + 哈希表，可以同步到一个循环里面写
            但是出于可读性，还是分了两个循环
        */ 
        // 前缀和
        int nums_len = nums.size();
        vector<int> pre_sum(nums_len + 1, 0);
        for (int i = 1; i <= nums_len; ++i) {
            pre_sum[i] = pre_sum[i - 1] + (nums[i - 1] == 0 ? -1 : 1);
        }
        // 利用哈希表记录先后出现的位置,计算两个位置之间的距离就可以得到最大的长度
        unordered_map<int, int> rec_sum;
        // rec_sum[i] = k， 总和为i的数组的长度是k
        rec_sum[0] = 0;
        int max_len = 0;
        for (int i = 1; i <= nums_len; ++i) {
            if (rec_sum.count(pre_sum[i])) {
                // rec_sum[pre_sum[i]] 就是上次出现同样数值的位置
                max_len = max(max_len, i - rec_sum[pre_sum[i]]);
            } else {
                // 只记录第一次出现的位置，其他位置不行。
                rec_sum[pre_sum[i]] = i;
            }
        }
        return max_len;
    }
};