Contiguous Array
给一个0,1数组, 返回最长的0和1相等的子数组. 这个直接count也能做, 但是我看讨论中有一个解法更巧妙. 先把0变成-1, 以为n个0和1个0想加是没有区别的, 所以变成-1就可以知道有几个-1了, 然后只需要找相同的sum就可以找到-1和1的相同的位置, 只需要记录最多的个数就可以.
public class Solution {
public int findMaxLength(int[] nums) {
for(int i = 0 ; i < nums.length; i++){
if(nums[i] == 0)
nums[i] = -1;
}
Map<Integer, Integer> map = new HashMap<>();
map.put(0,-1);
int sum = 0;
int max = 0;
for(int i = 0 ; i < nums.length; i++){
sum += nums[i];
if(map.containsKey(sum))
max = Math.max(max, i - map.get(sum));
else
map.put(sum,i);
}
return max;
}
}