3-26 阿里笔试第一题

[Douc1998]

/**
 * 阿里 3.26 笔试第一题
 * 环形数组，切两刀且成两个数组，让两个数组的元素和相等则算一种方案，求问一共多少种方案
 * ======================
 * 解题思路：前缀和 + Map 存储
 */

// 不使用 Map 存储，双 for 循环会超时
function getAllResult(arr){
    let len = arr.length;
    let count = 0;
    let preSum = [arr[0]];
    // 计算前缀和并存储
    for(let i = 1; i < len; i++){
        preSum.push(preSum[i - 1] + arr[i]);
    }

    // 不论是 i 还是 j，在位置 index 切，都是切在 index 对应数的后面，也就是会算上 index 这个数
    // i 不用切在第 0 个数前面，因为 j 切到最后一个数后面和这种情况是等效的。
    for(let i = 0; i < len - 1; i++){
        for(let j = i; j < len; j++){
            let sum1 = preSum[j] - preSum[i];
            let sum2 = preSum[len - 1] - preSum[j] + preSum[i];
            if(sum1 === sum2){
                console.log(i, j)
                count++;
            }
        }
    }
    return count;
}

let arr = [1, 2, -1, 2];
console.log(getAllResult(arr)); // 2

// 使用 Map 存储：前缀和 - 对应前缀和元素所在位置的集合
// 降低时间复杂度
function getAllResult(arr){
    let len = arr.length;
    let count = 0;
    let preSum = [arr[0]];
    // 计算前缀和并存储
    for(let i = 1; i < len; i++){
        preSum[i] = preSum[i - 1] + arr[i];
    }

    let sum = preSum[len - 1];
    if(sum % 2 === 1) return count; // 如果数组所有元素总和不是偶数，那肯定不存在分两个数组元素和相等

    // 用于记录前缀和有几种，对应的元素编号是多少
    let preSumMap = {};
    for(let i = 0; i < len; i++){
        if(preSum[i] in preSumMap){
            preSumMap[preSum[i]].push(i);
        }else{
            preSumMap[preSum[i]] = [i];
        }
    }

    // 遍历前缀和数组
    for(let i = 0; i < len; i++){
        let pre = preSum[i] - sum / 2; // 找出当前切割位置需要的另一个切割位置的前缀和值
        if(pre in preSumMap){
            // 如果另一个切割位置在当前位置的前面，就符合，因为我们是用 preSum[i] - sum / 2
            for(let j = 0; j < preSumMap[pre].length; j++){
                if(j < i){
                    count++
                }
            }
        }
    }
    return count;
}

console.log(getAllResult(arr)); // 2