LintCode连续数组

这个题目的名字翻译的不好，题意是：

给一个二进制数组，找到 0 和 1 数量相等的子数组的最大长度
样例
样例 1:
输入: [0,1]
输出: 2
解释: [0, 1] 是具有相等数量的 0 和 1 的最长子数组。
样例 2:
输入: [0,1,0]
输出: 2
解释: [0, 1] (或者 [1, 0]) 是具有相等数量 0 和 1 的最长子数组。
注意事项
给出的二进制数组的长度不会超过 50,000。

一个暴力型的O(n^3)的解法，妥妥的TLE:

const findMaxLength = function (nums) {
    // Write your code here
    var l = nums.length;
    while(l>0){
        for(var j = 0;j<=nums.length-l;j++){
            const filterLength = nums.filter((x,i)=>{
                    return x===1 && i>=j && i < l-j;
            }).length;
            if(l/2=== filterLength){
                return l;
            }
        }
        l--;
    }
    return 0;
}

最后将所有的0视为-1，题目就变成了求和为0的最小数组，同时如果以零点为起点，长度为i，j的子数组的和一样，那么以i为起点，j为末尾结点的子数组的和即为0，利用Map的性质，最后是O(n)复杂度的算法：

const findMaxLength = function (nums) {
    // Write your code here
    var dp = [0];
    for(let i = 1;i<=nums.length;i++){
        dp[i] = dp[i-1] + (nums[i-1]>0?1:-1);
    }
    var map = new Map();
    var max = 0;
    for(let i = 0; i<dp.length;i++){
        if(map.get(dp[i])!==undefined){
            max = Math.max(max,i-map.get(dp[i]));
        }else{
            map.set(dp[i],i);
        }
    }
    return max;
}