LeetCode-Go 题解 | 1664. Ways to Make a Fair Array：两种前缀和思路构造平衡数组

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 arraynums. 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 官方示例示例 1Input: nums [2,1,6,4] Output: 1逐一验证四种删除方案删除下标 0剩余[1,6,4]偶数位和 145奇数位和 6不平衡删除下标 1剩余[2,6,4]偶数位和 246奇数位和 6平衡删除下标 2剩余[2,1,4]偶数位和 246奇数位和 1不平衡删除下标 3剩余[2,1,6]偶数位和 268奇数位和 1不平衡。因此答案为1。示例 2Input: nums [1,1,1] Output: 3删除任意一个下标后剩余两个元素之和都相等都是 1三个下标全部可行。示例 3Input: nums [1,2,3] Output: 0三种删除方案均无法得到平衡数组。1.3 数据约束约束取值范围数组长度nums.length1 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位置没有变化奇偶性保持不变后缀部分原下标i1 ~ n-1整体左移一位奇偶性完全翻转——原来的偶数位变成了奇数位原来的奇数位变成了偶数位。于是删除后偶数位和 evenPrefix oddSuffix 奇数位和 oddPrefix evenSuffix注意这里的oddSuffix/evenSuffix是包含待删除元素的后缀和因此在计算交叉项时需要先减掉删除元素自身的影响。文档中的做法是在进入第i轮判断之前先把nums[i]从对应奇偶的后缀和中减去使后缀和变为i1 ~ 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的奇偶性但比较相等性时无需关心相等则ressum[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.gowaysToMakeFair与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.modGo 版本要求为 1.19。在仓库根目录下可直接针对该题运行测试go test -v -run Test_Problem1664 ./leetcode/1664.Ways-to-Make-a-Fair-Array/若需生成全仓覆盖率报告可参考 gotest.sh 中给出的命令go test -covermodeatomic -coverprofilecoverage.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），仅供参考