Problem
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
example 1
1
2
3
|
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
|
example 2
1
2
3
|
Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
|
Constraints
- The length of the given binary array will not exceed 50,000.
Solution
- init
sum
- walk throw givven array ,and
sum++ if current elemen(nums[idx]) equeal 1, and sum-- if current element equal -1
- if in map exist elemant with key
sum, compare idx-m[sum]+1 and max; if max if less – set max=idx-m[sum]+1
- Set to map
m[sum] = idx+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
func findMaxLength(nums []int) int {
max := 0
m := make(map[int]int, 0)
s:=0
m[0]=0
for idx:=range nums {
if nums[idx] == 1{
s+=1
} else {
s-=1
}
_, ok := m[s]
if ok {
if idx-m[s]+1>max {
max = idx-m[s]+1
}
} else {
m[s] = idx+1
}
}
return max
}
|