525. Contiguous Array

525. Contiguous Array

题目描述

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.

Note: The length of the given binary array will not exceed 50,000.

题目大意

求数组中 01 个数一样的最长子数组。

解题思路

主要思路是将 0 换成 -1 进行相加。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
func findMaxLength(_ nums: [Int]) -> Int {
var dict = [0: -1]
var sum = 0
var ml = 0
for (i, num) in (nums.enumerated()) {
sum += num == 0 ? -1 : 1
if let v = dict[sum] {
ml = max(ml, i - v)
}else {
dict[sum] = i
}
}
return ml
}
}
0%