拆分成最多数目的正偶数之和

记牢这套贪心:从 2 起一个个往上取,取不动为止,最后把剩下的零头并进末位。下面从 2 开始一步步走。

先看阶梯,这一排 2,4,6 一直到 16 是我们候选的偶数,从左到右由小到大。目标是把 60 拆开,右边结果集现在是空的,剩余就是 60。

动手前先看奇偶。若干个正偶数相加一定是偶数,所以只有偶数才可能拆得出。60 是偶数,能拆;如果 finalSum 是奇数,这里就直接返回空数组了。

为什么从 2 开始,因为要个数最多,每个数就得尽量小。数越小,同样的和里能塞进的个数就越多。所以指针停在阶梯最左边的 2 上,准备取第一个数。

看候选 2。现在剩余是 60,它不小于 2,说明还够取下这个 2,那就取。

把 2 收进结果集,它变绿。剩余相应减掉 2,从 60 变成 58。结果集现在有 1 个数了。

看候选 4。现在剩余是 58,它不小于 4,说明还够取下这个 4,那就取。

把 4 收进结果集,它变绿。剩余相应减掉 4,从 58 变成 54。结果集现在有 2 个数了。

看候选 6。现在剩余是 54,它不小于 6,说明还够取下这个 6,那就取。

把 6 收进结果集,它变绿。剩余相应减掉 6,从 54 变成 48。结果集现在有 3 个数了。

看候选 8。现在剩余是 48,它不小于 8,说明还够取下这个 8,那就取。

把 8 收进结果集,它变绿。剩余相应减掉 8,从 48 变成 40。结果集现在有 4 个数了。

看候选 10。现在剩余是 40,它不小于 10,说明还够取下这个 10,那就取。

把 10 收进结果集,它变绿。剩余相应减掉 10,从 40 变成 30。结果集现在有 5 个数了。

看候选 12。现在剩余是 30,它不小于 12,说明还够取下这个 12,那就取。

把 12 收进结果集,它变绿。剩余相应减掉 12,从 30 变成 18。结果集现在有 6 个数了。

看候选 14。现在剩余是 18,它不小于 14,说明还够取下这个 14,那就取。

把 14 收进结果集,它变绿。剩余相应减掉 14,从 18 变成 4。结果集现在有 7 个数了。

轮到候选 16 时,剩余只有 4,已经小于 16,取不动了。贪心到此打住,不能再往阶梯右边取新的数。现在结果集里有 7 个数,手上还攥着 4 的零头没处理。

这点零头 4 不能单开一个数,因为它比阶梯上还没取的偶数都小,单开要么和已取的重复要么破坏互不相同。稳妥的办法是把它加到最后取的那个 14 上,14 加 4 变成 18。18 和前面的数都不一样,个数也没减少,剩余清零。

验一下。结果集是 2、4、6、8、10、12、18,把它们加起来正好等于 60,而且两两互不相同。一共 7 个数,这就是能拆出的最多个数。

回放整个过程:从 2 起一路往上取,取到 14 时剩余不够再往上取,就把剩下的 4 并进 14 变成 18。最终答案是 2、4、6、8、10、12、18,共 7 个,任意顺序返回都算对。

边界想清:2 只能拆一个、4 取 2 后剩余并回也只有一个、奇数返回空、28 拆成四个数。

面试重点:贪心取最小使个数最多、零头并入末位保互异、大范围要用 64 位整数。