LeetCode (525) - Contiguous Array

下のTitleをクリックして、問題ページに移動します.
- Contiguous Array

Acceptance: 46.1%

Difficulty: Medium

問題の説明
Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

1 <= nums.length <= 10^5

nums[i] is either 0 or 1 .

例1

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1.

例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.

問題を解く

0と1の個数が同じサブアレイ.

・total = 0のうち、値が0異面-1、1異面+1の場合、0と1の個数に等しい.

進行中total = 0・index = iの場合、以前の総額でnが出現した場合(index=m)、サブアレイ(m,n)はtotal=0となる.

上記の情報を格納するためにMapを用いてtotalをキー値で格納し、value値をindexで格納する.

コード#コード#

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findMaxLength(int[] nums) {
        int total = 0, result = 0;
        Map<Integer, Integer> map = new HashMap<>();

        for (int index = 0, length = nums.length; index < length; index++) {
            int number = nums[index] == 1 ? 1 : -1;

            total += number;
            if (total == 0) {
                result = Math.max(result, index + 1);
            }

            if (map.containsKey(total)) {
                result = Math.max(result, index - map.get(total));
            } else {
                map.put(total, index);
            }
        }

        return result;
    }
}