525. Contiguous Array
Description
Given a binary array nums
, return the maximum length of a contiguous subarray with an equal number of 0
and 1
.
Example 1:
Input: nums = [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.
Example 2:
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.
Constraints:
1 <= nums.length <= 105
nums[i]
is either0
or1
.
Solutions
Solution 1: Prefix Sum + Hash Table
According to the problem description, we can treat $0$s in the array as $-1$. In this way, when encountering a $0$, the prefix sum $s$ will decrease by one, and when encountering a $1$, the prefix sum $s$ will increase by one. Therefore, suppose the prefix sum $s$ is equal at indices $j$ and $i$, where $j < i$, then the subarray from index $j + 1$ to $i$ has an equal number of $0$s and $1$s.
We use a hash table to store all prefix sums and their first occurrence indices. Initially, we map the prefix sum of $0$ to $-1$.
As we iterate through the array, we calculate the prefix sum $s$. If $s$ is already in the hash table, then we have found a subarray with a sum of $0$, and its length is $i - d[s]$, where $d[s]$ is the index where $s$ first appeared in the hash table. If $s$ is not in the hash table, we store $s$ and its index $i$ in the hash table.
The time complexity is $O(n)$, and the space complexity is $O(n)$, where $n$ is the length of the array.
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|