LeetCode-Go 题解 | 1664. Ways to Make a Fair Array：两种前缀和思路构造平衡数组
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
导读
本篇基于 LeetCode-Go 仓库中 1664. Ways to Make a Fair Array 题解文档 展开，深入剖析第 1664 题「生成平衡数组的方案数」：给定一个整数数组，恰好删除一个下标（删除后下标会重新排列）后，若奇数下标之和与偶数下标之和相等，则该数组称为"平衡数组"。读完本篇你将掌握两种时间复杂度均为 O(n) 的实现——基于前缀和/后缀和推导的常规写法，以及省略奇偶判断的超简洁写法，并理解二者之间的等价关系与推导过程。
一、题目回顾：删除一个元素后如何定义"公平"
1.1 题目原文
You are given an integer array
nums. You can chooseexactly oneindex (0-indexed) and remove the element. Notice that the index of the elements may change after the removal.
也就是说，我们只能且必须删除一个下标对应的元素。删除之后，数组长度减一，剩余元素的下标整体前移，因此每个元素的新下标奇偶性相对于原数组可能发生翻转。
An array isfairif the sum of the odd-indexed values equals the sum of the even-indexed values.
若删除后剩余数组的奇数下标元素之和等于偶数下标元素之和，则该数组是平衡（fair）的。题目要求返回所有能使删除后数组平衡的下标个数。
1.2 官方示例
示例 1：
Input: nums = [2,1,6,4] Output: 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，不平衡。
因此答案为1。
示例 2：
Input: nums = [1,1,1] Output: 3删除任意一个下标后，剩余两个元素之和都相等（都是 1），三个下标全部可行。
示例 3：
Input: nums = [1,2,3] Output: 0三种删除方案均无法得到平衡数组。
1.3 数据约束
| 约束 | 取值范围 |
|---|---|
数组长度nums.length | 1 <= nums.length <= 10^5 |
元素值nums[i] | 1 <= nums[i] <= 10^4 |
数组最长可达十万量级，这意味着任何每次删除后重新扫描求和的做法（O(n²)）都会超时，必须利用前缀信息做 O(1) 的增量推导。这也正是题解文档反复强调"暴力会超时"的原因。
二、暴力思路为何不可行
最直接的思路是：枚举每个待删除的下标i，模拟删除后重新构建数组，再分别累加奇偶下标元素和并比较。该过程对每个i都需要 O(n) 的遍历，总体复杂度为 O(n²)。在n = 10^5的数据规模下需要执行约 10^10 次操作，必然超时。
核心矛盾在于：每次删除元素后都重新计算奇偶数位总和，大量重复劳动被浪费。合理的方式是利用"前面已经计算过的累加和"推导出删除后的新状态，让单次判断降到 O(1)，总复杂度降为 O(n)。
三、解法二：前缀和 + 后缀和（可读性优先）
题解文档把这一思路命名为"前缀和，后缀和"，源码位于 1664. Ways to Make a Fair Array.go，对应函数waysToMakeFair1。
3.1 核心推导
设evenPrefix/oddPrefix分别表示原数组中位于当前下标i之前的偶数位、奇数位元素累加和；evenSuffix/oddSuffix分别表示包含当前下标i在内（即从i到数组末尾）的偶数位、奇数位元素累加和。
删除下标i之后，剩余数组由两部分拼接而成：
- 前缀部分（原下标
0 ~ i-1）：位置没有变化，奇偶性保持不变； - 后缀部分（原下标
i+1 ~ n-1）：整体左移一位，奇偶性完全翻转——原来的偶数位变成了奇数位，原来的奇数位变成了偶数位。
于是删除后：
偶数位和 = evenPrefix + oddSuffix 奇数位和 = oddPrefix + evenSuffix注意这里的oddSuffix/evenSuffix是包含待删除元素的后缀和，因此在计算交叉项时需要先减掉删除元素自身的影响。文档中的做法是：在进入第i轮判断之前，先把nums[i]从对应奇偶的后缀和中减去，使后缀和变为i+1 ~ n-1这一段；同时前缀和仍保持0 ~ i-1这一段，二者合起来正好是删除后的完整数组。
3.2 代码实现
// 解法二 前缀和，后缀和 func waysToMakeFair1(nums []int) int { evenPrefix, oddPrefix, evenSuffix, oddSuffix, res := 0, 0, 0, 0, 0 for i := 0; i < len(nums); i++ { if i%2 == 0 { evenSuffix += nums[i] } else { oddSuffix += nums[i] } } for i := 0; i < len(nums); i++ { if i%2 == 0 { evenSuffix -= nums[i] } else { oddSuffix -= nums[i] } if (evenPrefix + oddSuffix) == (oddPrefix + evenSuffix) { res++ } if i%2 == 0 { evenPrefix += nums[i] } else { oddPrefix += nums[i] } } return res }3.3 逐行解读
- 第一轮循环：扫一遍数组，把偶数位元素累加到
evenSuffix、奇数位元素累加到oddSuffix，得到包含全部元素的后缀和； - 第二轮循环（每次迭代处理一个候选下标
i）：- 先从对应奇偶的后缀和中扣掉
nums[i]，此时evenSuffix/oddSuffix精确表示i之后那半段； - 用交叉公式
evenPrefix + oddSuffix与oddPrefix + evenSuffix判断是否平衡，相等则res++； - 最后把
nums[i]累加进对应的前缀和，供下一轮使用。
- 先从对应奇偶的后缀和中扣掉
这个"先减后缀、再判相等、后加前缀"的三步流程，正是题解文档中描述的核心思想：删除元素后面，原来偶数位的总和变成了奇数位，原来奇数位的总和变成偶数位；后半段的总和可以用后缀和直接得到。
3.4 复杂度分析
- 时间复杂度：O(n)，两轮线性扫描，每轮迭代内均为 O(1) 运算；
- 空间复杂度：O(1)，仅使用常数个累加变量，没有额外数组。
四、解法一：省略奇偶判断的超简洁写法
题解文档指出，通过解法二的思考可以进一步抽象：每次变换后的操作本质上是"减去一个数 → 判断是否相等 → 再加上一个数"三步，解法二只是在这三步中额外判断了奇偶性。
4.1 关键洞察：奇偶性随删除自动翻转
为什么可以完全省略奇偶判断？因为每次删除一个元素后，数组的整体结构发生了一次奇偶错位：上一次的奇数和，在删除发生后天然变成了下一次的偶数和。只要用sum[i%2]与sum[1-(i%2)]这对互补下标来动态维护两个桶，奇偶翻转就被自动吸收进下标计算中，无需显式分支。
4.2 代码实现
// 解法一 超简洁写法 func waysToMakeFair(nums []int) int { sum, res := [2]int{}, 0 for i := 0; i < len(nums); i++ { sum[i%2] += nums[i] } for i := 0; i < len(nums); i++ { sum[i%2] -= nums[i] if sum[i%2] == sum[1-(i%2)] { res++ } sum[1-(i%2)] += nums[i] } return res }4.3 逐行解读
- 第一轮循环：
sum[0]累加所有偶数位元素，sum[1]累加所有奇数位元素（i%2天然完成下标分组）； - 第二轮循环处理下标
i时：sum[i%2] -= nums[i]：把当前元素从它所处的奇偶桶中拿走，模拟"删除"；- 比较
sum[i%2]与sum[1-(i%2)]：此时两个桶恰好分别代表删除后数组的偶数和与奇数和（具体哪个对应哪个，取决于i的奇偶性，但比较相等性时无需关心）； - 相等则
res++； sum[1-(i%2)] += nums[i]：把元素放回另一个桶，模拟"删除后下标翻转"，供下一轮使用。
整个过程把解法二中的四次奇偶分支（后缀减、交叉比较、前缀加）压缩成两个对称表达式，代码量减半，但逻辑完全等价。
4.4 复杂度分析
- 时间复杂度：O(n)，两轮循环；
- 空间复杂度：O(1)，仅一个长度为 2 的数组
sum。
五、两种解法的等价性与选择建议
| 对比维度 | 解法一（waysToMakeFair） | 解法二（waysToMakeFair1） |
|---|---|---|
| 核心思想 | 动态维护两个奇偶桶，删除后元素自动翻转进对侧桶 | 显式维护前缀和/后缀和，交叉求和 |
| 奇偶判断 | 通过i%2与1-(i%2)对称下标隐式处理 | 显式if i%2 == 0分支 |
| 代码量 | 约 10 行 | 约 20 行 |
| 可读性 | 简洁但对初学者有一定跳跃性 | 思路直白，易于对照推导 |
| 时间/空间 | O(n) / O(1) | O(n) / O(1) |
两种解法的时间、空间复杂度完全一致，差异只在代码表达。面试或笔试中建议优先采用解法一——它更短、更不容易在奇偶分支上出错；如果需要在讲解中让对方理解"为什么删一个元素奇偶会翻转"，则用解法二逐步推导更直观。题解文档也明确说明：解法二是理解的基础，解法一是抽象后的最优形态。
六、仓库配套：源码实现与测试用例验证
6.1 源码与测试位置
- 实现源码：1664. Ways to Make a Fair Array.go：
waysToMakeFair与waysToMakeFair1两个函数同文件共存，便于对照阅读； - 测试用例：1664. Ways to Make a Fair Array_test.go：采用仓库统一的"para/ans 结构体 + 表格驱动"测试风格。
6.2 测试数据与预期
测试文件 1664. Ways to Make a Fair Array_test.go 覆盖了四组用例：
输入nums | 期望输出 | 覆盖点 |
|---|---|---|
[6,1,7,4,1] | 0 | 题目原文的推导示例，无可行删除方案 |
[2,1,6,4] | 1 | 官方示例 1，恰有一个下标可行 |
[1,1,1] | 3 | 官方示例 2，全部下标可行（边界：全相等数组） |
[1,2,3] | 0 | 官方示例 3，无解 |
其中[6,1,7,4,1]正是题目描述中用来解释"删除后下标会改变"的数组，测试直接沿用了题目上下文，保证了两份实现与题目语义的一致性。运行测试时，Test_Problem1664会同时调用waysToMakeFair与waysToMakeFair1两个版本，可相互印证结果一致。
6.3 如何本地运行验证
仓库以github.com/halfrost/LeetCode-Go为模块名（见 go.mod），Go 版本要求为 1.19+。在仓库根目录下可直接针对该题运行测试：
go test -v -run Test_Problem1664 ./leetcode/1664.Ways-to-Make-a-Fair-Array/若需生成全仓覆盖率报告，可参考 gotest.sh 中给出的命令：
go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...七、举一反三：从本题抽象出的通用技巧
1664 题背后的方法论值得沉淀：
- 删除导致的奇偶翻转：删除下标
i后，i之后的所有元素下标奇偶性翻转。凡涉及"删除一个元素后按奇偶分组求和"的题目，都可以套用这一规律。 - 前缀和/后缀和的增量维护：与其每次重新扫描，不如预先计算好两侧的信息，再在单次遍历中 O(1) 维护。这是处理"枚举删除点"类问题的通用范式。
- 用对称下标压缩分支：
sum[i%2]与sum[1-(i%2)]这类互补写法，能显著减少奇偶分支代码，是 LeetCode-Go 仓库中常见的高效表达风格，适合在保持正确性的前提下精简代码。
理解解法二的推导过程、掌握解法一的精简表达，是本篇题解最值得吸收的两层价值。读者可以结合 源码文件 与 测试文件 反复对照，直至两种写法都能熟练手写。
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
