525.Contiguous_Array
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
Example
Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.
方法
用HashMap存储数最早开始的位置，key为值，value为位置。把0变成-1。实际原理如下图所示，在x轴上相等点的距离最长，则包含最多相等数量的0和1。因为对于相等的y值从第一次到第二次，路径和为0，即表示有相等数量的0和1，所以x轴相等点的距离越长，则表示有越多的相等数量的0和1。
public class Solution {
public int findMaxLength(int[] nums) {
for(int i = 0; i < nums.length; i++){
if(nums[i] == 0){
nums[i] = -1;
}
}
HashMap<Integer,Integer> hashMap = new HashMap<Integer,Integer>();
//key是值，value是位置
hashMap.put(0,-1);
int sum = 0;
int max = 0;
for(int i = 0; i < nums.length; i++){
sum = sum + nums[i];
if(hashMap.containsKey(sum)){
max = Math.max(max,i-hashMap.get(sum));
}else{
hashMap.put(sum,i);
}
}
return max;
}
}