C语言重构【1664】生成平衡数组的方案数

左手的ㄟ右手 2022-11-11 14:50 172阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给你一个整数数组 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

#### 方案： ####

*  题目给的是奇偶下标和，所以我们应当先求出奇偶数下标的和，以删除数为分界，将其分成左右两部分，左侧为正常奇偶下标和，右侧奇下标和变成欧下标和，偶的变奇，此时反过来加一下判断一下即可，直到最后。

class Solution
    { 
    public:
        int waysToMakeFair(vector<int> &nums)
        { 
            int odd_sum = 0, even_sum = 0;
            int len = nums.size();
            int res = 0;
            int n_odd_sum = 0, n_even_sum = 0;
            //奇偶元素下标元素求和
            for (int i = 0; i < len; i++)
            { 
                if (i % 2 == 0)
                    even_sum += nums[i];
                else
                    odd_sum += nums[i];
            }
    
            for (int i = 0; i < len; i++)
            { 
                if (i % 2 == 0)
                { 
                    //偶数位和-=
                    even_sum -= nums[i];
                    if (n_odd_sum + even_sum == n_even_sum + odd_sum)
                        res++;
                    n_even_sum += nums[i];
                }
                else
                { 
                    //奇数位和-=
                    odd_sum -= nums[i];
                    if (n_odd_sum + even_sum == n_even_sum + odd_sum)
                        res++;
                    n_odd_sum += nums[i];
                }
            }
            return res;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode