Leetcode 525 - Contiguous Array

Note:

• It’s not easy to come up with a presum soltution.
• My intuition was sliding window but realize it cannot capture the longest length cuz when 0 and 1‘s number are not equal, we can still move right instead of shrinking the window by moving left.
• Convert all 0 into -1, then this question becomes a problem of finding the max length with sum 0.
• Then use presum[], and store presum[i] into a hash set as we iterate.
• If an interval [i, j] meets the requirement of sum 0, then we have presum[j] - presum[i - 1] === 0, which means presum[j] = presum[i - 1].
• Note that there might be multiple presum[i] with same value, so map value should an array.

Question:

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

Example:

Code: