525. Contiguous Array
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
Example 1:
Input: [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
Example 2:
Input: [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.
Note: The length of the given binary array will not exceed 50,000.
class Solution { public int findMaxLength(int[] nums) { Map<Integer, Integer> map = new HashMap<>(); int maxlen = 0, count = 0; for(int i = 0;i < nums.length;i++) { count += (nums[i] == 1)?1:-1; // Array from index 0 to i contains equal number of 0's and 1's if(count == 0) maxlen = Math.max(maxlen, i+1); if(map.containsKey(count)) { maxlen = Math.max(maxlen, i - map.get(count)); } else map.put(count, i); } return maxlen; } }
设置一个map存放count，index的pair。计算count，nums是1就+1，是0就-1，然后有三种情况：count==0说明此时满足1==0数量，更新maxlen；map包含了count，那就用当前的index减去上一个count的index；不包含count，put进map