525 Contiguous Array

Posted on

525 Contiguous Array

1
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

找到连续的子数组，包含相同个数的0和1.

看到解法才想到之前看到过的微软的一到面试题，找出数组中的最长的和为0的字数组（好像是这样，忘记了），

如果遍历数组的话，找到一段符合要求的还要判断能不能和前面满足要求的子数组连起来，求最大值。

求和，如果当前sum(i)等于之前某个位置的sum(j)，说明这中间为0，sum(i)-sum(j)就行了。

回到这一题，按照原来的想法看，思路完全是一样的，当前子数组都有可能和之前的子数组连起来。把0变成-1就和之前的题一模一样了。

1
2
3
4
5
6
7
8
for(int i;i<length;i++){
	sum+=nums[i];
	if(map.containsKey(sum)){
		max=Math.max(max,i-map.get(sum));
	}else{
		map.put(sum,i);
	}
}