1664. 生成平衡数组的方案数.md

1664. 生成平衡数组的方案数

• 奇偶前缀和

/**
 *
 * @description 删除下标k之后,下标k左边的数字奇偶性不变,右边的数字奇偶性互换
 * @see https://leetcode-cn.com/problems/ways-to-make-a-fair-array/solution/qi-ou-bian-huan-kan-bu-dong-ni-lai-da-wo-by-treasu/
 * @param {number[]} nums
 * @return {*}  {number}
 */
function waysToMakeFair(nums: number[]): number {

    if (nums.length === 1) {
        return 1;
    }

    const oddPresum: number[] = [], // 奇数前缀和
        evenPresum: number[] = [], // 偶数前缀和
        length: number = nums.length;

    for (let i = 0; i < length; ++i) {
        if (i & 1) { // 下标是奇数
            oddPresum[i] = (oddPresum[i - 2] || 0) + nums[i]; // 计算奇数和
            evenPresum[i] = evenPresum[i - 1] || 0; // 别忘了,前缀和是累加起来的,所以不能断
        } else { // 下标是偶数
            evenPresum[i] = (evenPresum[i - 2] || 0) + nums[i];// 计算偶数和
            oddPresum[i] = oddPresum[i - 1] || 0;// 别忘了,前缀和是累加起来的,所以不能断
        }
    }

    let count: number = 0;

    for (let i = 0; i < length; ++i) {
        const oddSum = (oddPresum[i - 1] || 0) + evenPresum[length - 1] - evenPresum[i]; // 统计奇数和 
        const evenSum = (evenPresum[i - 1] || 0) + oddPresum[length - 1] - oddPresum[i]; // 统计偶数和

        if (oddSum === evenSum) {
            ++count;
        }
    }

    return count;
};