题目描述
思路解析动画文字版
记牢这条主线:删一个下标,只有它右边的元素奇偶位会对调,左边不动。所以新的偶数位之和等于左段偶位和加右段奇位和,新的奇数位之和等于左段奇位和加右段偶位和,两边相等就平衡。下面每一帧都在套这条线。
准备 · 求原总偶位和：正式开扫前,先把两个总和算出来备用。绿色标的是偶数下标 0、2、4 上的元素,分别是 1、3、2,加起来是 6,这就是整条数组原本的偶位和,记作 s1。它的用处是:后面任意一段右段的偶位和,都能用这个总和减去左段的偶位和得到;只有被删的正好落在偶下标时,才要再把它也扣掉,不用每次重新加。
准备 · 求原总奇位和：再把奇数下标 1、3、5 上的元素 2、3、1 加起来,得到 6,这是整条数组原本的奇位和,记作 s2。现在两个总和都有了,s1 是 6、s2 是 6。接下来从左到右逐个下标试着删,用左段前缀和加这两个总和,快速算出删掉它之后两边各是多少。
删下标 0 · 拆左右两段：现在试着删下标 0 这个元素 1,它被标成红色。它左边蓝色那段位置完全没动,奇偶位照旧;它右边绿色那段每个元素都往左挪一格,下标减 1,奇偶位整体对调。这一次它在最左边,没有左段,整个数组都是被对调的右段。下一帧把两段的和拼起来,看新数组两边各是多少。
删下标 0 · 拼两边的和：把两段拼起来算。删除后的新偶数位之和,等于左段原偶位和 0,加上右段原奇位和 6,因为右段奇位挪进了偶位,合起来是 6。删除后的新奇数位之和,等于左段原奇位和 0,加上右段原偶位和 5,合起来是 5。注意右段的偶位和奇位都是拿总和直接减出来的,没有重新逐个相加,这就是省时间的地方。
删下标 0 · 不平衡：比一比:新偶和 6 和新奇和 5 并不相等,删掉下标 0 之后两边不平衡,这个删法不算数,方案数 ans 保持 0 不变。
删下标 1 · 拆左右两段：现在试着删下标 1 这个元素 2,它被标成红色。它左边蓝色那段位置完全没动,奇偶位照旧;它右边绿色那段每个元素都往左挪一格,下标减 1,奇偶位整体对调。左右两段就这样分好了。下一帧把两段的和拼起来,看新数组两边各是多少。
删下标 1 · 拼两边的和：把两段拼起来算。删除后的新偶数位之和,等于左段原偶位和 1,加上右段原奇位和 4,因为右段奇位挪进了偶位,合起来是 5。删除后的新奇数位之和,等于左段原奇位和 0,加上右段原偶位和 5,合起来是 5。注意右段的偶位和奇位都是拿总和直接减出来的,没有重新逐个相加,这就是省时间的地方。
删下标 1 · 平衡：比一比:新偶和 5 正好等于新奇和 5,两边相等,删掉下标 1 之后数组是平衡的。这是一个有效方案,累计方案数 ans 从 0 加到 1。把这个下标记下来。
删下标 2 · 拆左右两段：现在试着删下标 2 这个元素 3,它被标成红色。它左边蓝色那段位置完全没动,奇偶位照旧;它右边绿色那段每个元素都往左挪一格,下标减 1,奇偶位整体对调。左右两段就这样分好了。下一帧把两段的和拼起来,看新数组两边各是多少。
删下标 2 · 拼两边的和：把两段拼起来算。删除后的新偶数位之和,等于左段原偶位和 1,加上右段原奇位和 4,因为右段奇位挪进了偶位,合起来是 5。删除后的新奇数位之和,等于左段原奇位和 2,加上右段原偶位和 2,合起来是 4。注意右段的偶位和奇位都是拿总和直接减出来的,没有重新逐个相加,这就是省时间的地方。
删下标 2 · 不平衡：比一比:新偶和 5 和新奇和 4 并不相等,删掉下标 2 之后两边不平衡,这个删法不算数,方案数 ans 保持 1 不变。
删下标 3 · 拆左右两段：现在试着删下标 3 这个元素 3,它被标成红色。它左边蓝色那段位置完全没动,奇偶位照旧;它右边绿色那段每个元素都往左挪一格,下标减 1,奇偶位整体对调。左右两段就这样分好了。下一帧把两段的和拼起来,看新数组两边各是多少。
删下标 3 · 拼两边的和：把两段拼起来算。删除后的新偶数位之和,等于左段原偶位和 4,加上右段原奇位和 1,因为右段奇位挪进了偶位,合起来是 5。删除后的新奇数位之和,等于左段原奇位和 2,加上右段原偶位和 2,合起来是 4。注意右段的偶位和奇位都是拿总和直接减出来的,没有重新逐个相加,这就是省时间的地方。
删下标 3 · 不平衡：比一比:新偶和 5 和新奇和 4 并不相等,删掉下标 3 之后两边不平衡,这个删法不算数,方案数 ans 保持 1 不变。
删下标 4 · 拆左右两段：现在试着删下标 4 这个元素 2,它被标成红色。它左边蓝色那段位置完全没动,奇偶位照旧;它右边绿色那段每个元素都往左挪一格,下标减 1,奇偶位整体对调。左右两段就这样分好了。下一帧把两段的和拼起来,看新数组两边各是多少。
删下标 4 · 拼两边的和：把两段拼起来算。删除后的新偶数位之和,等于左段原偶位和 4,加上右段原奇位和 1,因为右段奇位挪进了偶位,合起来是 5。删除后的新奇数位之和,等于左段原奇位和 5,加上右段原偶位和 0,合起来是 5。注意右段的偶位和奇位都是拿总和直接减出来的,没有重新逐个相加,这就是省时间的地方。
删下标 4 · 平衡：比一比:新偶和 5 正好等于新奇和 5,两边相等,删掉下标 4 之后数组是平衡的。这是一个有效方案,累计方案数 ans 从 1 加到 2。把这个下标记下来。
删下标 5 · 拆左右两段：现在试着删下标 5 这个元素 1,它被标成红色。它左边蓝色那段位置完全没动,奇偶位照旧;它右边绿色那段每个元素都往左挪一格,下标减 1,奇偶位整体对调。这一次它在最右边,没有右段,左段原封不动。下一帧把两段的和拼起来,看新数组两边各是多少。
删下标 5 · 拼两边的和：把两段拼起来算。删除后的新偶数位之和,等于左段原偶位和 6,加上右段原奇位和 0,因为右段奇位挪进了偶位,合起来是 6。删除后的新奇数位之和,等于左段原奇位和 5,加上右段原偶位和 0,合起来是 5。注意右段的偶位和奇位都是拿总和直接减出来的,没有重新逐个相加,这就是省时间的地方。
删下标 5 · 不平衡：比一比:新偶和 6 和新奇和 5 并不相等,删掉下标 5 之后两边不平衡,这个删法不算数,方案数 ans 保持 2 不变。
收束 · 有效方案回看：六个下标都试了一遍。绿色标出的下标 1 和 4 是仅有的两个有效方案:删下标 1 后两边都是 5,删下标 4 后两边也都是 5。其余四个下标删完都不平衡,被压成灰色。整个过程从左扫到右,前缀和 t1、t2 一路滚动,两个总和减一减就拿到右段,没有任何重复求和。
完成 · 答案 2：把有效方案数一汇总:能让数组变平衡的删除下标一共有 2 个,所以答案是 2。拿暴力法核对一遍,nums = [1, 2, 3, 3, 2, 1] 里确实只有删下标 1 和删下标 4 这两种删法能得到平衡数组,对得上。一遍线性扫,靠前缀和加两个总和,就把每个下标都判完了。
边界:单个元素删完是空数组算平衡给 1、三个相同元素三种删法全平衡给 3、[1,2,3] 删哪个都不平衡给 0。
面试重点:朴素重拼求和 O(n²) 到前缀和 O(n);只需左右各两个和拼一拼、不用真移动元素;0 和相等元素不构成坑,空数组算平衡。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def waysToMakeFair(self, nums: List[int]) -> int: s1, s2 = sum(nums[::2]), sum(nums[1::2]) ans = t1 = t2 = 0 for i, v in enumerate(nums): ans += i % 2 == 0 and t2 + s1 - t1 - v == t1 + s2 - t2 ans += i % 2 == 1 and t2 + s1 - t1 == t1 + s2 - t2 - v t1 += v if i % 2 == 0 else 0 t2 += v if i % 2 == 1 else 0 return ans复杂度
- 时间：O(n)，n 是数组长度。第一遍扫求两个总和,第二遍扫逐个下标判平衡,每个下标都是常数次加减和一次比较,合起来线性
- 空间：O(1)，只用 s1、s2、t1、t2、ans 这几个标量,峰值占用与 n 无关。动画里画的两段账面板是帮助理解的教学辅助,不是算法必需
易错点
面试追问把动画讲成自己的话
追问最朴素的做法是什么,为什么慢?
追问为什么删掉一个元素就能把整段奇偶位讲清楚,不用真的去移动元素?
追问数组里有 0 或者元素相等会不会有坑?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
使数组互补的最少操作次数
LeetCode 1674 · 中等 · 沿着 数组套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题