文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個整數數組 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 <= 10^5 1 <= nums[i] <= 10^4

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/ways-to-make-a-fair-array
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 正反雙向的奇偶前綴和都求出來
• 刪除某個元素后，逆向的奇偶后綴和需要交換

class Solution { public:int waysToMakeFair(vector<int>& nums) {int n = nums.size();int i = 0, odd = 0, even = 0;vector<int> odd1(n, 0), odd2(n, 0), even1(n, 0), even2(n, 0);for(i = 0, odd = 0, even = 0; i < n; i++) {if(i%2 == 1){odd1[i] = odd;//除了i下標，之前的奇數和even1[i] = even;//奇數下標之前的偶數下標之和odd += nums[i];}else{even1[i] = even;//除了i下標，之前的偶數和odd1[i] = odd;even += nums[i];}}for(i = n-1, odd = 0, even = 0; i >= 0; i--) {if(i%2 == 1){odd2[i] = odd;//除了i下標，之后的奇數和even2[i] = even;odd += nums[i];}else{even2[i] = even;//除了i下標，之后的偶數和odd2[i] = odd;even += nums[i];}}int ans = 0;for(int i = 0; i < n; ++i){ //刪除 i 了，后序的偶數和變成奇數和//奇數和變成偶數和if(odd1[i]+even2[i] == even1[i]+odd2[i])ans++;}return ans;} };

332 ms 109.5 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1664. 生成平衡数组的方案数（前缀和+后缀和）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。