生成平衡数组的方案数【LC1664】
给你一个整数数组 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 是 平衡数组 的 方案数 。
出去玩好累 不想出去玩了
预处理+枚举
- 思路：
。枚举每一个删除的位置，判断删除后奇数下标元素之和与偶数下标元素之和是否相等。假设删除的下标为i，那么nums[0,i-1]范围内的奇偶性不变，nums[i+1,n-1]范围内的下标奇偶性倒置，奇数下标变为偶数下标，偶数下标变为奇数下标。由此可得：
- 删除后奇数下标元素之和=nums[0,i-1]中奇数下标元素之和+nums[i+1,n-1]中偶数下标元素之和
- 删除后偶数下标元素之和=nums[0,i-1]中偶数下标元素之和+nums[i+1,n-1]中奇数下标元素之和
。因此可以计算原数组的奇数下标元素和偶数下标元素的前缀和数组oddSum和evenSum，快速计算出某个范围内的奇数之和或者偶数之和
- oddSum[i]代表前i个奇数之和
- evenSum[i]代表前i个偶数之和
- 实现：两个前缀和数组
class Solution { public int waysToMakeFair(int[] nums) { int n = nums.length; if (n == 1) return 1; int[] oddSum = new int[n]; int[] evenSum = new int[n]; // 初始化前缀和数组 evenSum[0] = nums[0]; evenSum[1] = nums[0]; oddSum[1] = nums[1]; int count = 0; for (int i = 2; i < n; i++){ if (i % 2 == 0){ evenSum[i] = evenSum[i - 2] + nums[i]; oddSum[i] = oddSum[i - 1]; }else{ oddSum[i] = oddSum[i - 2] + nums[i]; evenSum[i] = evenSum[i - 1]; } } // 枚举每个下标 for (int i = 0; i < n; i++){ int odd = i >= 1 ? oddSum[i - 1] : 0; odd += evenSum[n - 1] - evenSum[i]; int even = i >= 1 ? evenSum[i - 1] : 0; even += oddSum[n - 1] - oddSum[i]; if (even == odd){ count++; } } return count; } }
。复杂度分析
- 时间复杂度：O ( n )
- 空间复杂度：O ( n )
- 优化1：思路同上，枚举每个位置i ，仍是将和分为两个部分odd和even，使用int变量代替前缀和数组，优化空间复杂度。
。首先预处理得到原始数组的偶数下标元素之和s 1 和奇数下标之和s 2，并记录当前枚举到的偶数下标之和t 1 以及奇数下标之和t 2
。然后计算两个和，由于删除下标i ii后，奇偶性倒置，因此根据i ii进行处理
odd=nums[0,i-1]中奇数下标元素之和+nums[i+1,n-1]中偶数下标元素之和
even=nums[0,i-1]中偶数下标元素之和+nums[i+1,n-1]中奇数下标元素之和
- 若i为偶数
even=t1+s2−t2
odd=t2+s1−t1−nums[i]
- 若i为奇数
even=t1+s2−t2−nums[i]
odd=t2+s1−t1
class Solution { public int waysToMakeFair(int[] nums) { int s1 = 0, s2 = 0; int n = nums.length; for (int i = 0; i < n; ++i) { s1 += i % 2 == 0 ? nums[i] : 0; s2 += i % 2 == 1 ? nums[i] : 0; } int t1 = 0, t2 = 0; int ans = 0; for (int i = 0; i < n; ++i) { int v = nums[i]; ans += i % 2 == 0 && t2 + s1 - t1 - v == t1 + s2 - t2 ? 1 : 0; ans += i % 2 == 1 && t2 + s1 - t1 == t1 + s2 - t2 - v ? 1 : 0; t1 += i % 2 == 0 ? v : 0; t2 += i % 2 == 1 ? v : 0; } return ans; } } 作者：ylb 链接：https://leetcode.cn/problems/ways-to-make-a-fair-array/solutions/2078792/by-lcbin-3jl3/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
。复杂度分析
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
- 优化2：将优化1中的4个变量化简成一个变量s=odd1−even1−odd2+even2
。首先将所有偶数下标元素累加至s，将所有奇数下标累减至s
。然后枚举每个i ii，当i ii为奇数时累加，为偶数时减，当 s == 0 时答案加一
把 odd1 + even2 == odd2 + even1 变形得 odd1 - even1 == odd2 - even2，这样可以化简成两个变量 s1 = odd1 - even1 和 s2 = odd2 - even2，如果 s1 == s2 答案就加一。s1 和 s2 的更新就是 i 为奇数加，为偶数减。
再变形成 s1 - s2 == 0，那么令 s = s1 - s2，就可以化简成一个变量了，当 s == 0 时答案加一。
class Solution { public int waysToMakeFair(int[] nums) { int n = nums.length; int s = 0, count = 0; for (int i = 0; i < n; i++){ s += i % 2 == 0 ? nums[i] : -nums[i];// 后 } for (int i = 0; i < n; i++){ s += i % 2 == 0 ? -nums[i] : nums[i];// 前+? if (s == 0) count++; s += i % 2 == 0 ? -nums[i] : nums[i];// 后+? } return count; } }
。复杂度分析
- 时间复杂度：O ( n )
- 空间复杂度：O ( 1 )
