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.
比较巧妙的一道题，正常写的话会TLE，参考答案的思路是，设置一个计数，如果遇到1，则+1， 遇到0， 则-1。这样的话会有这种结论：当出现两个index他们的值相等的时候，说明，他们之间的1的个数刚好等于0的个数。
代码：
public int findMaxLength2(int[] nums) { if(nums == null || nums.length == 0) return 0; HashMap<Integer, Integer> map = new HashMap<>(); int count = 0; map.put(0, 0); for(int i=0;i<nums.length;i++) { if(nums[i] == 1) { count++; } map.put(i+1, count); } int length = nums.length; while(length>0) { if(length % 2 != 0) { length--;continue; } for(int i=0;i<=nums.length-length;i++) { if((map.get(i+length) - map.get(i)) == (length/2)) { // 这里减法不用+1， 因为就是算的差的部分的长度 return length; } } length-=2; } return 0; }这里的i 理解为： 在i之前的部分的和。
public int findMaxLength(int[] nums) { if(nums == null || nums.length == 0) return 0; HashMap<Integer, Integer> map = new HashMap<>(); map.put(0, 0);//index = -1, value = 0 int count = 0; int maxLength = 0; for(int i=0;i<nums.length;i++) { count += nums[i] == 1 ? 1: -1; if(map.containsKey(count)) { maxLength = Math.max(maxLength, i+1 - map.get(count)); } else { map.put(count, i+1); } } return maxLength; }
