题目地址
https://leetcode.com/problems/contiguous-array/
题目描述
525. Contiguous Array
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.
思路
- 前缀和. 由于要求的是最长长度的连续数组有相等的1和0, 可以理解为如何求得最长一段区间和为0的子数组.
- 如果当前num等于1, 则前缀和数组+1, 否则-1.
- 如果当前位置的sum值已经存在, 则比较长度.
- 取最大长度返回即可.
关键点
代码
- 语言支持:Java
class Solution {
public int findMaxLength(int[] nums) {
int n = nums.length;
int[] preSums = new int[n + 1];
for (int i = 1; i <= n; i++) {
if (nums[i - 1] == 1) {
preSums[i] = preSums[i - 1] + 1;
} else {
preSums[i] = preSums[i - 1] - 1;
}
}
Map<Integer, Integer> map = new HashMap<>();
int max = 0;
for (int i = 0; i <= n; i++) {
if (map.containsKey(preSums[i])) {
max = Math.max(max, i - map.get(preSums[i]));
}
map.putIfAbsent(preSums[i], i);
}
return max;
}
}
网友评论