当前位置 博文首页 > 唐梓航-求职中的博客:leetcode-525. 连续数组
???首先对原数组做处理,将所有的0都变为-1;这样一来 “含有相同数量的 0 和 1 的连续数组” 就等价为 “元素值总和为0的连续数组”。
? ? 其后,从头扫一遍数组,并记录当前的前缀和的值,将该值和对应的下标存入到一个标记数组或哈希表中。若该前缀和的值已出现过(即标记数组或哈希中已存在),则说明标记中的下标到当前扫描的下标的这段数组的总和值是为0的。
? ? 打个例子: [?-1,-1,-1,1,-1,1,-1,1,-1,-1,-1,-1 ] 在扫描完到第四个元素时,前缀和为-2 且未记录过,则将值-2和下标3记录起来。当扫描到??[?-1,-1,-1,1,-1,-1,1,1,-1,-1,-1,-1 ]? , 此时得到的前缀和为-2,且知道标记中有记录过-2,则说明此刻下标到之前记录的下标的这段数组总和为0??[?-1,-1,-1,1,-1,-1,1,1,-1,-1,-1,-1 ]? 。
?
class Solution {
public int findMaxLength(int[] nums) {
int ans = 0,sum = 0;
for(int i=0;i<nums.length;i++)if(nums[i]==0)nums[i]=-1;
HashMap<Integer,Integer> map = new HashMap();
for(int i=0;i<nums.length;i++) {
sum+=nums[i];
if(sum == 0) { if(i >= ans) ans = i+1; }
if(map.get(sum) == null) { map.put(sum,i); continue; }
int temp = i - map.get(sum);
if(temp > ans) ans=temp;
}
return ans;
}
}
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> sumToIndex = new HashMap<>();
sumToIndex.put(0, -1);
int sum = 0, max = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sumToIndex.containsKey(sum)) {
max = Math.max(max, i - sumToIndex.get(sum));
}
else {
sumToIndex.put(sum, i);
}
}
return max;
}
}
?
cs