拆分成最多数目的正偶数之和 图解题解
这道题到底在问什么
- 输入
- finalSum = 12
- 输出
- [2,4,6] （2 加 4 加 6,三个数最多）
- 输入
- finalSum = 7
- 输出
- [] （奇数,凑不出）
最优解：一步一步想明白
- 3记牢这套贪心:从 2 起一个个往上取,取不动为止,最后把剩下的零头并进末位。下面从 2 开始一步步走。
- 4先看阶梯,这一排 2,4,6 一直到 16 是我们候选的偶数,从左到右由小到大。目标是把 60 拆开,右边结果集现在是空的,剩余就是 60。
- 5动手前先看奇偶。若干个正偶数相加一定是偶数,所以只有偶数才可能拆得出。60 是偶数,能拆;如果 finalSum 是奇数,这里就直接返回空数组了。
- 6为什么从 2 开始,因为要个数最多,每个数就得尽量小。数越小,同样的和里能塞进的个数就越多。所以指针停在阶梯最左边的 2 上,准备取第一个数。
- 7看候选 2。现在剩余是 60,它不小于 2,说明还够取下这个 2,那就取。
- 8把 2 收进结果集,它变绿。剩余相应减掉 2,从 60 变成 58。结果集现在有 1 个数了。
- 9看候选 4。现在剩余是 58,它不小于 4,说明还够取下这个 4,那就取。
- 10把 4 收进结果集,它变绿。剩余相应减掉 4,从 58 变成 54。结果集现在有 2 个数了。
- 11看候选 6。现在剩余是 54,它不小于 6,说明还够取下这个 6,那就取。
- 12把 6 收进结果集,它变绿。剩余相应减掉 6,从 54 变成 48。结果集现在有 3 个数了。
- 13看候选 8。现在剩余是 48,它不小于 8,说明还够取下这个 8,那就取。
- 14把 8 收进结果集,它变绿。剩余相应减掉 8,从 48 变成 40。结果集现在有 4 个数了。
- 15看候选 10。现在剩余是 40,它不小于 10,说明还够取下这个 10,那就取。
- 16把 10 收进结果集,它变绿。剩余相应减掉 10,从 40 变成 30。结果集现在有 5 个数了。
- 17看候选 12。现在剩余是 30,它不小于 12,说明还够取下这个 12,那就取。
- 18把 12 收进结果集,它变绿。剩余相应减掉 12,从 30 变成 18。结果集现在有 6 个数了。
- 19看候选 14。现在剩余是 18,它不小于 14,说明还够取下这个 14,那就取。
- 20把 14 收进结果集,它变绿。剩余相应减掉 14,从 18 变成 4。结果集现在有 7 个数了。
- 21轮到候选 16 时,剩余只有 4,已经小于 16,取不动了。贪心到此打住,不能再往阶梯右边取新的数。现在结果集里有 7 个数,手上还攥着 4 的零头没处理。
- 22这点零头 4 不能单开一个数,因为它比阶梯上还没取的偶数都小,单开要么和已取的重复要么破坏互不相同。稳妥的办法是把它加到最后取的那个 14 上,14 加 4 变成 18。18 和前面的数都不一样,个数也没减少,剩余清零。
- 23验一下。结果集是 2、4、6、8、10、12、18,把它们加起来正好等于 60,而且两两互不相同。一共 7 个数,这就是能拆出的最多个数。
- 24回放整个过程:从 2 起一路往上取,取到 14 时剩余不够再往上取,就把剩下的 4 并进 14 变成 18。最终答案是 2、4、6、8、10、12、18,共 7 个,任意顺序返回都算对。
⚠️ 容易写错的地方
✗ 错：从大偶数往下取
✓ 对：必须从最小的 2 起往上取
要个数最多就得每个数尽量小,从大数取会让总个数变少
✗ 错：把剩余零头单独开一个新数
✓ 对：把零头并入最后取的那个数
零头比下一个候选偶数还小,单开会和已取的数重复或破坏互不相同
✗ 错：用 int 存 finalSum
✓ 对：C 加加用 long long、Java 用 long
finalSum 最大到十的十次方,超过 int 上限会溢出
✗ 错：忘记先判奇偶
✓ 对：奇数直接返回空数组
若干正偶数之和一定是偶数,奇数永远凑不出来
完整代码（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 maximumEvenSplit(self, finalSum: int) -> List[int]:
if finalSum & 1:
return []
ans = []
i = 2
while i <= finalSum:
finalSum -= i
ans.append(i)
i += 2
ans[-1] += finalSum
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:
vector<long long> maximumEvenSplit(long long finalSum) {
vector<long long> ans;
if (finalSum % 2) {
return ans;
}
for (long long i = 2; i <= finalSum; i += 2) {
ans.push_back(i);
finalSum -= i;
}
ans.back() += finalSum;
return ans;
}
};Java
import java.util.*;
class Solution {
public List<Long> maximumEvenSplit(long finalSum) {
List<Long> ans = new ArrayList<>();
if (finalSum % 2 == 1) {
return ans;
}
for (long i = 2; i <= finalSum; i += 2) {
ans.add(i);
finalSum -= i;
}
ans.add(ans.remove(ans.size() - 1) + finalSum);
return ans;
}
}复杂度
时间
O(√finalSum)
取到第 k 个数时,取走的总和是 2 加 4 一直加到 2k,等于 k 乘 k 加 1,约等于 finalSum。所以取的个数 k 大约是根号 finalSum,循环就跑这么多轮
空间
O(√finalSum)
答案数组存的就是这大约根号 finalSum 个数。除去要返回的答案本身,只用了 i 和剩余量几个变量,额外空间是常数
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 拆分成最多数目的正偶数之和 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题为什么贪心就是对的?+
要让个数最多,等价于让每个数尽量小。从 2 起按 2,4,6 递增取是当前能选的最小的一组互不相同正偶数,取到不能再取为止,个数已经拉满。最后剩的零头小于下一个候选,没法再多凑出一个数,只能并入末位。可以用反证说明:若存在更多个数的拆法,它们的最小可能和会超过 finalSum,矛盾。
为什么剩余并入的是最后一个数而不是别的?+
因为末位是当前最大的数,加上一个更小的正偶数后仍然大于前面所有数,天然保持互不相同;若加到中间某个数上,可能和它后面的数相等而冲突。加到末位最省事也最安全。
数据范围要注意什么?+
finalSum 最大到十的十次方,超过 32 位 int 的范围,C 加加要用 long long、Java 要用 long,否则会溢出出错。取的个数只有根号量级,所以时间和空间都是根号 finalSum。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 拆分成最多数目的正偶数之和 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。