Leetcode 525. Contiguous Array

Leetcode 525. Contiguous Array

使用数组写起来麻烦一点，但hashmap运行速度会慢一点。

Approach #2 Using Extra Array [Accepted]

For example:

input: [1,1,1,1, 0]
return 2
count: [1,2,3,4,3]
3-3 ==0 return 4(index of next 2) -2(index of first 2)

public class Solution {
    public int findMaxLength(int[] nums) {
        int[] arr = new int[2 * nums.length + 1];
        Arrays.fill(arr, -2);
        arr[nums.length] = -1;
        int maxlen = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            count = count + (nums[i] == 0 ? -1 : 1);
            if (arr[count + nums.length] >= -1) {
                //如果count在过去出现过，更新maxlen
                maxlen = Math.max(maxlen, i - arr[count + nums.length]);
            } else {
                //arr记录第一次出现count的index
                arr[count + nums.length] = i;
            }
        }
        return maxlen;
    }
}

Approach #3 Using HashMap [Accepted]

public class Solution {

    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)) {
                maxlen = Math.max(maxlen, i - map.get(count));
            } else {
                map.put(count, i);
            }
        }
        return maxlen;
    }
}