Link to the problem

The problem is here: https://leetcode-cn.com/problems/contiguous-array/

Problem description

Given a binary array nums which consists of only 0 and 1, find the length of the longest subarray of
nums that has the equal number of 0’s and 1’s.

Idea

To simplify the problem, we set all 0’s in nums to be -1. Then the problem becomes: find the length of the longest subarray of nums that sums up to 0.

It can be solved by using the prefix-sum algorithm. We define lc-525 Contiguous Array - 图1, and for simplicity, lc-525 Contiguous Array - 图2. The problem is to find with lc-525 Contiguous Array - 图3 and lc-525 Contiguous Array - 图4.

Implementation

My implementation is this:

  1. int findMaxLength(vector<int>& nums) {
  2.     unordered_map<int, int> mp;
  3.     mp[0] = -1;
  4.     int sum = 0, ans = 0;
  5.     for (int i = 0; i < nums.size(); i++) {
  6.         if (nums[i]) {
  7.             sum++;
  8.         } else {
  9.             sum--;
  10.         }
  11.         auto it = mp.find(sum);
  12.         if (it != mp.end()) {
  13.             ans = max(ans, i - it->second);
  14.         } else {
  15.             mp.insert({sum, i});
  16.         }
  17.     }
  18.     return ans;
  19. }

Note:

  • Do not need to convert 0 to -1 actually. Just use a variable to record the running sum.
  • Should only keep the position of the first occurrence of some sum because we are finding the longest subarray.