连续数组(Contiguous Array)

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

示例 1:

输入: [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。

示例 2:

输入: [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

注意: 给定的二进制数组的长度不会超过50000。

最粗暴的方式

int count0(int i,int j,int *nums) {
    int count = 0;
    for (int k =i; k<=j;k++){
        if(nums[k] == 0){
            count++;
        }
    }
    return count;
}
int count1(int i,int j,int *nums) {
    int count = 0;
    for (int k =i; k<=j;k++){
        if(nums[k] == 1){
            count++;
        }
    }
    return count;
}
int findMaxLength(int* nums, int numsSize){
    int maxLength = 0;
    for (int i =0;i<numsSize;i++){
        for(int j =i;j<numsSize;j++){
            if(count0(i,j,nums) == count1(i,j,nums)){
                int length = j-i+1;
                if (length > maxLength){
                    maxLength = length;
                }
            }
        }
    }
    return maxLength;
}

但是这样会超时，毕竟O(n^3)

改进后：

int findMaxLength(int* nums, int numsSize){
    int maxLength=0;
    for (int i =0;i<numsSize;i++){
        int count = 0;
        for (int j =i;j<numsSize;j++){
            if (nums[j]==0){
                count ++;
            }else{
                count--;
            }
            if(count == 0 && j-i+1>maxLength){
                maxLength = j-i+1;
            }
        }
    }
    return maxLength;
}

我简单进行了改进，发现测试用例过于恐怖，导致O(n^2)也会超时……

int cindex(int j){
    return j + 1;
}
int findex(int j,int numsSize){
    return j + numsSize;
}

int findMaxLength(int * nums,int numsSize){
    int countDiffSize = numsSize+1;
    int countDiff[countDiffSize];
    countDiff[cindex(-1)]=0;
    for(int i =0;i<numsSize;i++){
        if(nums[i]==0){
            countDiff[cindex(i)]=countDiff[cindex(i-1)]+1;
        } else {
            countDiff[cindex(i)] = countDiff[cindex(i-1)]-1;
        }
    }
    int findMaxJSize = 2*numsSize + 1;
    int findMaxJ[findMaxJSize];

    for(int k=-numsSize;k<numsSize;k++){
        findMaxJ[findex(k,numsSize)]=-1;
    }
    for(int j=0;j<numsSize;j++){
        findMaxJ[findex(countDiff[cindex(j)], numsSize)] = j;
    }

    int maxLength = 0;
    for (int i=0;i<numsSize;i++){
        int target = countDiff[cindex(i-1)];

        int length = findMaxJ[findex(target, numsSize)]-i+1;
        if(length > maxLength){
            maxLength = length;
        }
    }
    return maxLength;
}

典型的用空间换取时间