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

题目描述

给你一个整数数组 nums 。你需要选择 恰好 一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。

比方说，如果 nums = [6,1,7,4,1] ，那么：

• 选择删除下标 1 ，剩下的数组为 nums = [6,7,4,1] 。
• 选择删除下标 2 ，剩下的数组为 nums = [6,1,4,1] 。
• 选择删除下标 4 ，剩下的数组为 nums = [6,1,7,4] 。

如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 平衡数组 。

请你返回删除操作后，剩下的数组 nums 是 平衡数组 的 方案数 。

示例 1：

输入：nums = [2,1,6,4]
输出：1
解释：
删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。
删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。
删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。
删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。
只有一种让剩余数组成为平衡数组的方案。

示例 2：

输入：nums = [1,1,1]
输出：3
解释：你可以删除任意元素，剩余数组都是平衡数组。

示例 3：

输入：nums = [1,2,3]
输出：0
解释：不管删除哪个元素，剩下数组都不是平衡数组。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

思路

根据题目内容，输入是一个数组，长度为n，我们需要依次删除i=0到i=n-1的坐标对应的数，然后进行奇数坐标和偶数坐标数值和的计算，常规的思路下，我们按照题目的步骤进行计算，需要n的平方的时间复杂度，根据题目的提示，n的大小为10的5次方，将会超时。
我们可以观察删除对应坐标后剩下的数组的一些规律，以数组nums=[0,1,2,3,4,5,6]为例

• 删除偶数坐标对应的数组值，例如删除i=2的情况，则数组被切分为两部分，一部分是坐标2之前的数组[0,1]，一个是坐标2之后的数组[3,4,5,6],可以计算发现，如果删除坐标2后数组为平衡数组，则坐标2之前的数组的奇数项加上坐标2之后的偶数项的和要等于坐标2之前数组的偶数项加上坐标2之后的奇数项之后，我们分别用odd0,odd1代表删除坐标前和后的奇数项和，用even0和even1代表删除坐标前和后的偶数项和。则可以发现：在even0+odd1==odd0+even1下，数组平衡。

• 同样的删除奇数坐标，也有相同的结论，则我们可以根据这个结论进行预先计算出所有奇数项和和偶数项和，然后在通过一次遍历获取结果。

题解

class Solution {
    //[0,1,2,3,4,5,6,7]
    //i==even i==2 : even0+odd1==odd0+even1
    //i==odd i==3  : even0+odd1==odd0+ even1
    public int waysToMakeFair(int[] nums) {
        int n=nums.length,res=0;
        int odd0=0,odd1=0,even0=0,even1=0;
        for(int i=0;i<n;i++){
            if(i%2==0){
                even1+=nums[i];
            }
            else{
                odd1+=nums[i];
            }
        }
        for(int i=0;i<n;i++){
            if(i%2==0){
                even1-=nums[i];
            }
            else{
                odd1-=nums[i];
            }
            if(even0+odd1==odd0+even1){
                res++;
            }
            if(i%2==0){
                even0+=nums[i];
            }
            else{
                odd0+=nums[i];
            }
        }
        return res;
    }
}