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.

题目大意

求数组中 0 和 1 个数一样的最长子数组。

解题思路

主要思路是将 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%