给你一个整数数组 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
方法一:动态规划 思路与算法
首先题目给出一个下标从 0 开始长度为 n 的整数数组 nums,并给出「平衡数组」的定义:数组中奇数下标元素和与偶数下标元素的和相等。现在我们可以选择一个位置 i,0 \le i < n 的元素删除(注意删除后 i 之后的下标可能会因此发生改变)。我们需要求出所有删除该下标元素后的数组为「平衡数组」的下标数目。
我们设 preOdd}[i] 表示位置 i,0 \le i < n 前所有奇数位置元素的和,preEven}[i] 表示位置 i 前所有偶数位置元素的和,sufOdd}[i] 表示位置 i 后所有奇数位置元素的和,sufEven}[i] 表示位置 i 后所有偶数位置元素的和,我们来看如何进行状态转移——
当 i 为奇数时:
preOdd}[i + 1] = \textit{preOdd}[i] + \textit{nums}[i],i + 1 < n
sufOdd}[i] = \textit{sufOdd}[i - 1] - \textit{nums}[i],i - 1 \ge 0
preEven}[i + 1] = \textit{preEven}[i],i + 1 < n
sufEven}[i] = \textit{sufEven}[i - 1],i - 1 \ge 0
当 i 为偶数时:
preEven}[i + 1] = \textit{preEven}[i] + \textit{nums}[i],i + 1 < n
sufEven}[i] = \textit{sufEven}[i - 1] - \textit{nums}[i],i - 1 < n
preOdd}[i + 1] = \textit{preOdd}[i],i + 1 < n
sufOdd}[i] = \textit{sufOdd}[i - 1],i - 1 \ge 0
其中边界条件为:当 i = 0 时,preOdd}[0] = 0,preEven}[0] = 0,sufOdd}[0] = \sum_{2i + 1}^{n}\textit{nums}[2i + 1],sufEven}[0] = \sum_{2i}^{n}\textit{nums}[2i]。
不失一般性,现在我们将下标 i 的元素进行删除,显而易见下标 i 之前的元素下标并不会因此发生改变,而下标 i 之后的原本在 j,j > i 下标的数组元素会移动到下标 j - 1,即下标 i 之后的奇数下标元素会成为偶数下标元素,偶数下标元素会成为奇数下标元素。所以删除后数组中全部奇数下标元素和为 preOdd}[i] + \textit{sufEven}[i],全部偶数下标元素和为 preEven}[i] + \textit{sufOdd}[i],若两者相等则说明删除下标 i 后的数组为「平衡数组」。那么我们尝试删除每一个下标 i,0 \le i < n,来统计能生成「平衡数组」的下标即可。又因为 preOdd}[i],preEven}[i],sufOdd}[i],sufEven}[i] 求解都与前一个数有关,因此我们可以用「滚动数组」的技巧来进行空间优化。
代码
[sol1-Python3] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution : def waysToMakeFair (self, nums: List [int ] ) -> int : res = odd1 = even1 = odd2 = even2 = 0 for i, num in enumerate (nums): if i & 1 : odd2 += num else : even2 += num for i, num in enumerate (nums): if i & 1 : odd2 -= num else : even2 -= num if odd1 + even2 == odd2 + even1: res += 1 if i & 1 : odd1 += num else : even1 += num return res
[sol1-C++] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution {public : int waysToMakeFair (vector<int >& nums) { int odd1 = 0 , even1 = 0 ; int odd2 = 0 , even2 = 0 ; for (int i = 0 ; i < nums.size (); ++i) { if (i & 1 ) { odd2 += nums[i]; } else { even2 += nums[i]; } } int res = 0 ; for (int i = 0 ; i < nums.size (); ++i) { if (i & 1 ) { odd2 -= nums[i]; } else { even2 -= nums[i]; } if (odd1 + even2 == odd2 + even1) { ++res; } if (i & 1 ) { odd1 += nums[i]; } else { even1 += nums[i]; } } return res; } };
[sol1-Java] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public int waysToMakeFair (int [] nums) { int odd1 = 0 , even1 = 0 ; int odd2 = 0 , even2 = 0 ; for (int i = 0 ; i < nums.length; ++i) { if ((i & 1 ) != 0 ) { odd2 += nums[i]; } else { even2 += nums[i]; } } int res = 0 ; for (int i = 0 ; i < nums.length; ++i) { if ((i & 1 ) != 0 ) { odd2 -= nums[i]; } else { even2 -= nums[i]; } if (odd1 + even2 == odd2 + even1) { ++res; } if ((i & 1 ) != 0 ) { odd1 += nums[i]; } else { even1 += nums[i]; } } return res; } }
[sol1-C#] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 public class Solution { public int WaysToMakeFair (int [] nums ) { int odd1 = 0 , even1 = 0 ; int odd2 = 0 , even2 = 0 ; for (int i = 0 ; i < nums.Length; ++i) { if ((i & 1 ) != 0 ) { odd2 += nums[i]; } else { even2 += nums[i]; } } int res = 0 ; for (int i = 0 ; i < nums.Length; ++i) { if ((i & 1 ) != 0 ) { odd2 -= nums[i]; } else { even2 -= nums[i]; } if (odd1 + even2 == odd2 + even1) { ++res; } if ((i & 1 ) != 0 ) { odd1 += nums[i]; } else { even1 += nums[i]; } } return res; } }
[sol1-C] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 int waysToMakeFair (int * nums, int numsSize) { int odd1 = 0 , even1 = 0 ; int odd2 = 0 , even2 = 0 ; for (int i = 0 ; i < numsSize; ++i) { if (i & 1 ) { odd2 += nums[i]; } else { even2 += nums[i]; } } int res = 0 ; for (int i = 0 ; i < numsSize; ++i) { if (i & 1 ) { odd2 -= nums[i]; } else { even2 -= nums[i]; } if (odd1 + even2 == odd2 + even1) { ++res; } if (i & 1 ) { odd1 += nums[i]; } else { even1 += nums[i]; } } return res; }
[sol1-JavaScript] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 var waysToMakeFair = function (nums ) { let odd1 = 0 , even1 = 0 ; let odd2 = 0 , even2 = 0 ; for (let i = 0 ; i < nums.length ; ++i) { if ((i & 1 ) !== 0 ) { odd2 += nums[i]; } else { even2 += nums[i]; } } let res = 0 ; for (let i = 0 ; i < nums.length ; ++i) { if ((i & 1 ) != 0 ) { odd2 -= nums[i]; } else { even2 -= nums[i]; } if (odd1 + even2 === odd2 + even1) { ++res; } if ((i & 1 ) !== 0 ) { odd1 += nums[i]; } else { even1 += nums[i]; } } return res; };
[sol1-Golang] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 func waysToMakeFair (nums []int ) (res int ) { var odd1, even1, odd2, even2 int for i, num := range nums { if i&1 > 0 { odd2 += num } else { even2 += num } } for i, num := range nums { if i&1 > 0 { odd2 -= num } else { even2 -= num } if odd1+even2 == odd2+even1 { res++ } if i&1 > 0 { odd1 += num } else { even1 += num } } return }
复杂度分析
时间复杂度:O(n),其中 n 为数组 nums 的长度。
空间复杂度:O(1),仅使用常量空间。