Skip to main content

Contiguous Array

Tips

题目类型: 前缀和 + HashMap

相关题目:

Problem​

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

Constraints:
  • 1 <= nums.length <= 10⁵
  • nums[i] is either 0 or 1
Examples
Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Input: nums = [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Input: nums = [0,0,1,0,0,0,1,1]
Output: 6
Explanation: [0,0,1,0,0,0,1,1] is the longest contiguous subarray with equal number of 0 and 1.

Solution​

The key insight is to transform the problem: treat 0 as -1. Then finding a subarray with equal numbers of 0 and 1 becomes finding a subarray with sum equal to 0.

Why does this work?

  • If we have equal numbers of 0 and 1, say x zeros and x ones
  • Treating 0 as -1: sum = x * (-1) + x * 1 = 0

Algorithm:

  1. Transform 0 to -1 while building the prefix sum array
  2. Use a HashMap to store the first occurrence of each prefix sum
  3. When we see the same prefix sum again, it means the subarray between these two positions has sum 0 (equal 0s and 1s)
  4. Track the maximum length

Key Points:

  • Initialize map with {0: 0} to handle subarrays starting from index 0
  • Only store the first occurrence of each prefix sum to maximize length
  • When we see a repeated prefix sum, calculate the distance: i - map.get(sum)

Time Complexity: O(n) - single pass through the array Space Complexity: O(n) - HashMap storage and prefix sum array

function findMaxLength(nums: number[]): number {
  const n = nums.length
  const preSum = new Array(n + 1).fill(0)
  const map = new Map([[0, 0]]) // sum: first index
  let max = 0

  // Build prefix sum, treating 0 as -1
  for (let i = 0; i < n; i++) {
    preSum[i + 1] = preSum[i] + (nums[i] === 0 ? -1 : 1)
  }

  for (let i = 1; i <= n; i++) {
    const sum = preSum[i]
    if (map.has(sum)) {
      // Same prefix sum means equal 0s and 1s between these positions
      // Calculate the distance and update max
      max = Math.max(max, i - map.get(sum))
    } else {
      // Record the first occurrence of this prefix sum
      map.set(sum, i)
    }
  }

  return max
}

Example walkthrough:

For nums = [0, 1, 0]:

Transform to: [-1, 1, -1]

Build prefix sum:
preSum = [0, -1, 0, -1]

Initial: map = {0: 0}, max = 0

i=1, sum=-1:
  Not in map, store it
  map = {0: 0, -1: 1}

i=2, sum=0:
  0 exists at index 0! max = max(0, 2-0) = 2
  Found subarray [0,1] with length 2

i=3, sum=-1:
  -1 exists at index 1! max = max(2, 3-1) = 2
  Found subarray [1,0] with length 2

Result: max = 2

Optimization: You can combine the prefix sum calculation with the map lookup in a single loop:

function findMaxLength(nums: number[]): number {
  const map = new Map([[0, -1]]) // sum: first index (use -1 for empty prefix)
  let sum = 0
  let max = 0

  for (let i = 0; i < nums.length; i++) {
    sum += nums[i] === 0 ? -1 : 1

    if (map.has(sum)) {
      max = Math.max(max, i - map.get(sum))
    } else {
      map.set(sum, i)
    }
  }

  return max
}