今天的做过了
补一下昨天的 恨525
525. Contiguous Array
一开始就往subarray sum想
若nums[i:j]符合条件，表示sum[i:j] == (j-i+1)/2 (整除时)
原本想说就照这个条件，记下prefix sum，每个j都往前找各个i
但看了一下size <= 50000，想当然不是这样
后来发现其实只要把0都改成-1，
就只需要确认prefix sum与自己相等的那个地方就可以了
只需要用个map记下最早出现这个prefix sum的index即可
好像在哪里也用过这招，有点忘记了
int findMaxLength(vector<int>& nums) {
int n = nums.size();
unordered_map<int,int> mp;
int prefix = 0;
int ans = 0;
mp[0] = -1;
for(int i=0; i<n; i++)
{
prefix += (nums[i] == 0 ? -1 : 1);
if(mp.find(prefix) != mp.end())
{
ans = max(ans, i-mp[prefix]);
}
else
{
mp[prefix] = i;
}
}
return ans;
}