生成平衡数组的方案数 图解题解
这道题到底在问什么
- 输入
- nums = [2,1,6,4]
- 输出
- 1(删下标 1 得 [2,6,4],偶位 2+4=6 等于奇位 6)
- 输入
- nums = [1,1,1]
- 输出
- 3(删任意一个都平衡)
- 输入
- nums = [1,2,3]
- 输出
- 0(删哪个都不平衡)
先想最直接的笨办法
把有效方案数一汇总:能让数组变平衡的删除下标一共有 2 个,所以答案是 2。拿暴力法核对一遍,nums = [1, 2, 3, 3, 2, 1] 里确实只有删下标 1 和删下标 4 这两种删法能得到平衡数组,对得上。一遍线性扫,靠前缀和加两个总和,就把每个下标都判完了。（动画第 25 步）
最优解：一步一步想明白
- 3记牢这条主线:删一个下标,只有它右边的元素奇偶位会对调,左边不动。所以新的偶数位之和等于左段偶位和加右段奇位和,新的奇数位之和等于左段奇位和加右段偶位和,两边相等就平衡。下面每一帧都在套这条线。
- 4正式开扫前,先把两个总和算出来备用。绿色标的是偶数下标 0、2、4 上的元素,分别是 1、3、2,加起来是 6,这就是整条数组原本的偶位和,记作 s1。它的用处是:后面任意一段右段的偶位和,都能用这个总和减去左段的偶位和得到;只有被删的正好落在偶下标时,才要再把它也扣掉,不用每次重新加。
- 5再把奇数下标 1、3、5 上的元素 2、3、1 加起来,得到 6,这是整条数组原本的奇位和,记作 s2。现在两个总和都有了,s1 是 6、s2 是 6。接下来从左到右逐个下标试着删,用左段前缀和加这两个总和,快速算出删掉它之后两边各是多少。
- 6现在试着删下标 0 这个元素 1,它被标成红色。它左边蓝色那段位置完全没动,奇偶位照旧;它右边绿色那段每个元素都往左挪一格,下标减 1,奇偶位整体对调。这一次它在最左边,没有左段,整个数组都是被对调的右段。下一帧把两段的和拼起来,看新数组两边各是多少。
- 7把两段拼起来算。删除后的新偶数位之和,等于左段原偶位和 0,加上右段原奇位和 6,因为右段奇位挪进了偶位,合起来是 6。删除后的新奇数位之和,等于左段原奇位和 0,加上右段原偶位和 5,合起来是 5。注意右段的偶位和奇位都是拿总和直接减出来的,没有重新逐个相加,这就是省时间的地方。
- 8比一比:新偶和 6 和新奇和 5 并不相等,删掉下标 0 之后两边不平衡,这个删法不算数,方案数 ans 保持 0 不变。
- 9现在试着删下标 1 这个元素 2,它被标成红色。它左边蓝色那段位置完全没动,奇偶位照旧;它右边绿色那段每个元素都往左挪一格,下标减 1,奇偶位整体对调。左右两段就这样分好了。下一帧把两段的和拼起来,看新数组两边各是多少。
- 10把两段拼起来算。删除后的新偶数位之和,等于左段原偶位和 1,加上右段原奇位和 4,因为右段奇位挪进了偶位,合起来是 5。删除后的新奇数位之和,等于左段原奇位和 0,加上右段原偶位和 5,合起来是 5。注意右段的偶位和奇位都是拿总和直接减出来的,没有重新逐个相加,这就是省时间的地方。
- 11比一比:新偶和 5 正好等于新奇和 5,两边相等,删掉下标 1 之后数组是平衡的。这是一个有效方案,累计方案数 ans 从 0 加到 1。把这个下标记下来。
- 12现在试着删下标 2 这个元素 3,它被标成红色。它左边蓝色那段位置完全没动,奇偶位照旧;它右边绿色那段每个元素都往左挪一格,下标减 1,奇偶位整体对调。左右两段就这样分好了。下一帧把两段的和拼起来,看新数组两边各是多少。
- 13把两段拼起来算。删除后的新偶数位之和,等于左段原偶位和 1,加上右段原奇位和 4,因为右段奇位挪进了偶位,合起来是 5。删除后的新奇数位之和,等于左段原奇位和 2,加上右段原偶位和 2,合起来是 4。注意右段的偶位和奇位都是拿总和直接减出来的,没有重新逐个相加,这就是省时间的地方。
- 14比一比:新偶和 5 和新奇和 4 并不相等,删掉下标 2 之后两边不平衡,这个删法不算数,方案数 ans 保持 1 不变。
- 15现在试着删下标 3 这个元素 3,它被标成红色。它左边蓝色那段位置完全没动,奇偶位照旧;它右边绿色那段每个元素都往左挪一格,下标减 1,奇偶位整体对调。左右两段就这样分好了。下一帧把两段的和拼起来,看新数组两边各是多少。
- 16把两段拼起来算。删除后的新偶数位之和,等于左段原偶位和 4,加上右段原奇位和 1,因为右段奇位挪进了偶位,合起来是 5。删除后的新奇数位之和,等于左段原奇位和 2,加上右段原偶位和 2,合起来是 4。注意右段的偶位和奇位都是拿总和直接减出来的,没有重新逐个相加,这就是省时间的地方。
- 17比一比:新偶和 5 和新奇和 4 并不相等,删掉下标 3 之后两边不平衡,这个删法不算数,方案数 ans 保持 1 不变。
- 18现在试着删下标 4 这个元素 2,它被标成红色。它左边蓝色那段位置完全没动,奇偶位照旧;它右边绿色那段每个元素都往左挪一格,下标减 1,奇偶位整体对调。左右两段就这样分好了。下一帧把两段的和拼起来,看新数组两边各是多少。
- 19把两段拼起来算。删除后的新偶数位之和,等于左段原偶位和 4,加上右段原奇位和 1,因为右段奇位挪进了偶位,合起来是 5。删除后的新奇数位之和,等于左段原奇位和 5,加上右段原偶位和 0,合起来是 5。注意右段的偶位和奇位都是拿总和直接减出来的,没有重新逐个相加,这就是省时间的地方。
- 20比一比:新偶和 5 正好等于新奇和 5,两边相等,删掉下标 4 之后数组是平衡的。这是一个有效方案,累计方案数 ans 从 1 加到 2。把这个下标记下来。
- 21现在试着删下标 5 这个元素 1,它被标成红色。它左边蓝色那段位置完全没动,奇偶位照旧;它右边绿色那段每个元素都往左挪一格,下标减 1,奇偶位整体对调。这一次它在最右边,没有右段,左段原封不动。下一帧把两段的和拼起来,看新数组两边各是多少。
- 22把两段拼起来算。删除后的新偶数位之和,等于左段原偶位和 6,加上右段原奇位和 0,因为右段奇位挪进了偶位,合起来是 6。删除后的新奇数位之和,等于左段原奇位和 5,加上右段原偶位和 0,合起来是 5。注意右段的偶位和奇位都是拿总和直接减出来的,没有重新逐个相加,这就是省时间的地方。
- 23比一比:新偶和 6 和新奇和 5 并不相等,删掉下标 5 之后两边不平衡,这个删法不算数,方案数 ans 保持 2 不变。
- 24六个下标都试了一遍。绿色标出的下标 1 和 4 是仅有的两个有效方案:删下标 1 后两边都是 5,删下标 4 后两边也都是 5。其余四个下标删完都不平衡,被压成灰色。整个过程从左扫到右,前缀和 t1、t2 一路滚动,两个总和减一减就拿到右段,没有任何重复求和。
- 25把有效方案数一汇总:能让数组变平衡的删除下标一共有 2 个,所以答案是 2。拿暴力法核对一遍,nums = [1, 2, 3, 3, 2, 1] 里确实只有删下标 1 和删下标 4 这两种删法能得到平衡数组,对得上。一遍线性扫,靠前缀和加两个总和,就把每个下标都判完了。
⚠️ 容易写错的地方
✗ 错：以为删掉一个元素后整条数组奇偶位都翻转
✓ 对：只有被删元素右边的会奇偶对调,左边的位置没动、奇偶不变
删除只让被删位置右边的元素左移一格,左边元素下标完全没变,所以必须左右分开算
✗ 错：算右段和时忘了把被删的那个元素也减掉
✓ 对：右段偶位和 = s1 减左段偶位和 再减被删元素(若它在偶位)
总和 s1 包含了被删元素本身,只减左段不够,还要把被删的那个从它原本所属的奇偶位里扣掉,否则对应那一侧的和算多了
✗ 错：对每个下标都重新把剩余数组拼出来求两边和
✓ 对：用前缀 t1、t2 滚动,右段拿总和减出来,一遍线性
每个下标重拼再求和是 O(n) 每次,总共 O(n²),数据大就超时;前缀和让每个下标只花常数时间
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int waysToMakeFair(vector<int>& nums) {
int s1 = 0, s2 = 0;
int n = nums.size();
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;
ans += i % 2 == 1 && t2 + s1 - t1 == t1 + s2 - t2 - v;
t1 += i % 2 == 0 ? v : 0;
t2 += i % 2 == 1 ? v : 0;
}
return ans;
}
};Java
import java.util.*;
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;
}
}复杂度
时间
O(n)
n 是数组长度。第一遍扫求两个总和,第二遍扫逐个下标判平衡,每个下标都是常数次加减和一次比较,合起来线性
空间
O(1)
只用 s1、s2、t1、t2、ans 这几个标量,峰值占用与 n 无关。动画里画的两段账面板是帮助理解的教学辅助,不是算法必需
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 生成平衡数组的方案数 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
最朴素的做法是什么,为什么慢?+
最朴素就是枚举每个要删的下标,把剩下的元素重新拼成一个数组,再从头扫一遍求偶位和与奇位和判断是否相等。每个下标都要 O(n) 重拼加求和,一共 n 个下标,总复杂度 O(n²)。数据规模上万时就偏慢。用前缀和把它压到 O(n):右段的和靠总和减左段一步得到,每个下标只花常数时间。
为什么删掉一个元素就能把整段奇偶位讲清楚,不用真的去移动元素?+
因为我们不关心移动后每个元素具体落在哪,只关心两类和:偶位的总和与奇位的总和。删除只影响被删位置右边那段的奇偶归属,而那段是整体对调,等价于把右段原来的奇位和与偶位和互换角色。左段完全不受影响。所以用四个量左偶、左奇、右偶、右奇拼一拼就够,根本不用真的搬动数组。
数组里有 0 或者元素相等会不会有坑?+
不会。整个判断只是把若干元素相加再比较两个和是否相等,0 参与求和没有任何特殊性,元素相等也只是让某些下标同时成立而已。真正要小心的是边界:数组只有一个元素时删完是空数组,空数组两边和都是 0,要记得算作一个平衡方案。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 生成平衡数组的方案数 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。