leetcode525. Contiguous Array
leetcode525. 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.
假设现在有一个由0和1组成的整数数组，问该数组中0和1个数相等的最大的子数组长度。
思路一：暴力循环
假设我们能够算出来从下标0开始所有子数组中0和1的个数，得出numOfZero[i]和numOfOne[i]（其实这里无需用两个整数数组来记录，因为0-i这个子数组中1的个数一定等于i+1-numOfZero[i]。
再对所有子数组按照长度从大到小根据numOfZero开始寻找i-j中0和1相等的情况，一旦找到，就可以结束循环。因为这一定是最长的满足0和1数量相等的子数组。
public int findMaxLength(int[] nums) {
int[] numOfOne = new int[nums.length + 1];
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
numOfOne[i + 1] = numOfOne[i];
} else {
numOfOne[i + 1] = numOfOne[i] + 1;
}
}
int max;
boolean finish = false;
for (max = nums.length - nums.length % 2; max > 0; max -= 2) {
for (int j = 0; j + max < numOfOne.length; j++) {
int curNumOfOne = numOfOne[j+max] - numOfOne[j];
int curNumOfZero = max - curNumOfOne;
if (curNumOfOne == curNumOfZero) {
finish = true;
break;
}
}
if (finish) {
break;
}
}
return max;
}思路二：HASHMAP
换个思路来讲，如果将0视为-1，1还是视为1，则0，1个数相等的子数组中所有元素的和其实为0。假设i-j这个子数组中0和1个数相等，其实等价于0-(i-1)以及0-j这两个子数组中元素的和是相等。因此我们可以记录0-i子数组的元素和，一旦遇到相等的，就说明该?️在之前由某个子数组合成过，将两个下标相减即可得到满足条件的子数组的长度，
public int findMaxLength2(int[] nums) {
int n = nums.length;
int[] map = new int[nums.length * 2 + 1];
Arrays.fill(map, -2);
int sum = n;
map[n] = -1;
int max = 0;
for (int i = 0 ; i<nums.length ; i++) {
sum += (nums[i] * 2 - 1);
if (map[sum] == -2) {
map[sum] = i;
} else {
max = Math.max(max, i-map[sum]);
}
}
return max;
}