当前位置 博文首页 > 炸栈专家：leetcode 525. 连续数组
该题和之前做过的 leetcode 513.连续的子数组和 类似的方法。
只不过该题中规定的连续数组内容比较特殊，我们可以 将数组中的 0全部看作 -1 ，那么问题便简单多了。
我们只需寻找元素和为0的数组就行了，因为 数组和为0 则表示 有相同数量的 1和 -1相互抵消。把-1换成0便是符合题目规定的连续数组了。
哈希表中 key 为前缀和，val 为数组元素下标
C++：
class Solution {
public:
int findMaxLength(vector<int>& nums) {
int len=nums.size();
int ret=0;//函数返回值
if(len<2)//数组元素个数小于2则不满足连续数组的条件
return 0;
int sum=0;//前缀和的值
unordered_map<int,int> hash;//定义哈希表
hash[0]=-1;//存入前缀和key为0的下标值val为-1
for(int i=0;i<len;++i){
if(nums[i]==1)
++sum;//当前元素值为1则++sum
else
--sum;//当前元素为0时，把0当作-1，于是--sum 等于 sum+=(-1)
//查询哈希表中是否有key为sum的值
if(hash.count(sum)){
//如果哈希表中有前缀和与当前前缀和相同的值，则 i-hash[sum] 是连续数组的长度
ret=fmax(ret,i-hash[sum]);
}else{
//当哈希表没有和此次循环sum相同的值，则存入此次的sum值，以防后面的循环中有相同sum值
hash[sum]=i;
}
}
return ret;
}
};
C：
struct HashTable{
int key;
int val;
UT_hash_handle hh;
};
int findMaxLength(int* nums, int numsSize){
struct HashTable *hashtable=NULL;
struct HashTable *tmp=(struct HashTable *)malloc(sizeof(struct HashTable));
tmp->key=0;
tmp->val=-1;
HASH_ADD_INT(hashtable,key,tmp);
int ret=0;
int sum=0;
for(int a=0;a<numsSize;++a){
if(nums[a]==1)
sum++;
else
sum--;
struct HashTable *tmp;
HASH_FIND_INT(hashtable,&sum,tmp);
if(tmp!=NULL){
ret=fmax(ret,a-tmp->val);
}else{
tmp=(struct HashTable *)malloc(sizeof(struct HashTable));
tmp->key=sum;
tmp->val=a;
HASH_ADD_INT(hashtable,key,tmp);
}
}
return ret;
}
