[刷题防痴呆] 0525 - 连续数组 (Contiguous

题目地址

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;
    }
}