Explain - LeetCode 525 Contiguous Array

題目: Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1

解法:

1. 當遇到 0 就 -1, 遇到 1 就 +1, 計算每個陣列位置的加總
2. 最重要的概念就是: 當遇到相同的加總數字, 表示中間經歷了相同的 1 & 0.
3. 因此解法就是:
1. 走過所有的陣列, 計算每個位子的 count. 遇到 0 就 -1, 遇到 1 就 +1
2. 最重要的概念是: 當過程中出現相同的 count (不管正負) 就表示過程中有相同的 0 與 1
3. 因此解法就是一邊算與紀錄 count, 如果遇到相同的 count 就算距離, 把最長的距離記錄下來

Code

public class Solution {

    public static void main(String[] args) {

        new Solution().findMaxLength(new int[]{0,0,1,0,0,0,1,1});

    }

    public int findMaxLength(int[] nums) {

        Map<Integer, Integer> map = new HashMap<>();

        map.put(0, -1);

        int maxlen = 0, count = 0;

        for (int i = 0; i < nums.length; i++) {

            count = count + (nums[i] == 1 ? 1 : -1);

            if (map.containsKey(count)) { 2. 如果以前有過跟現在相同的 count, 表示過程中經歷了相同的 0 & 1

                maxlen = Math.max(maxlen, i - map.get(count)); // 3. 以此計算距離

            } else {

                map.put(count, i); // 1. 紀錄目前的 count 的位置

            }

        }

        return maxlen;

    }

}