美文网首页
[刷题防痴呆] 0525 - 连续数组 (Contiguous

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

作者: 西出玉门东望长安 | 来源:发表于2021-12-27 02:15 被阅读0次

    题目地址

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

    相关文章

      网友评论

          本文标题:[刷题防痴呆] 0525 - 连续数组 (Contiguous

          本文链接:https://www.haomeiwen.com/subject/tqwwfrtx.html