广安市网站建设_网站建设公司_网站开发_seo优化

乍一看可能想暴力求解（也就是三层循环硬找），但在数据量大的时候绝对会 TLE（超时）。其实，这道题披着算法的外衣，骨子里考的是一点点小学数论和贪心思想。

今天就把我的解题思路和代码分享出来，顺便聊聊为什么要这么写。

01. 核心思路：不要盯着数字看，要看“余数”

如果我们要判断一个数能不能被 3 整除，大家的第一反应可能是把它们加起来再% 3。但是，如果我们要从一堆数里凑出三个数，可能的情况太多了。

这里有一个关键的数学性质：

(a + b + c) \mod 3 的结果，完全取决于 (a%3 + b%3 + c%3) mod 3

也就是说，不管原来的数字是100还是1，对于“除以 3”这个问题来说，它们都是同一类人（余数都是 1）。

既然如此，我们完全不需要关心具体的数字是谁，只需要把原本复杂的数组，按照模 3 的余数拆分成三个阵营：

1. 余数党 0：比如 3, 0, 9, 12...

2. 余数党 1：比如 1, 4, 7, 10...

3. 余数党 2：比如 2, 5, 8, 11...

02. 寻找合法的“搭配公式”

把数字分类后，问题就变成了：怎么从这三个阵营里挑 3 个人，让它们的代表数字（余数）加起来能被 3 整除？

稍微排列组合一下，你会发现合法的组合只有这 4 种（简直少得可怜，这正是我们想要的）：

• 方案 A (0+0+0)：三个数都是 3 的倍数。余数和：$0+0+0=0$。

• 方案 B (1+1+1)：三个数余数都是 1。余数和：$1+1+1=3$，能被 3 整除。

• 方案 C (2+2+2)：三个数余数都是 2。余数和：$2+2+2=6$，能被 3 整除。

• 方案 D (0+1+2)：每个阵营各出一个。余数和：$0+1+2=3$，能被 3 整除。

其他的组合比如1+1+2（余数 4），0+2+2（余数 4）统统不行。

03. 代码实现：贪心就是“只选大的”

既然知道了合法的组合，为了让总和最大，我们肯定要在每个阵营里只选最大的那些数。

这时候，Python 的sort或者是优先队列就派上用场了。我选择了最直观的写法：分桶 -> 排序 -> 暴力比对。

下面是我的 Python 实现：

Python

class Solution: def maximumSum(self, nums: List[int]) -> int: zero, one, two = [], [], [] for n in nums: if n % 3 == 0: zero.append(n) elif n % 3 == 1: one.append(n) else: two.append(n) zero.sort(reverse=True) one.sort(reverse=True) two.sort(reverse=True) # 0,0,0 | 0,1,2 | 1,1,1 | 2,2,2 res = 0 if len(zero) >= 3: res = max(res, zero[0] + zero[1] + zero[2]) if len(one) >= 3: res = max(res, one[0] + one[1] + one[2]) if len(two) >= 3: res = max(res, two[0] + two[1] + two[2]) if zero and one and two: res = max(res, zero[0] + one[0] + two[0]) return res

代码复盘

这段代码其实非常有意思。

1. 为什么用列表而不是优先队列？

   虽然用大顶堆（Priority Queue）看起来更“算法”一点，但在 Python 里，list.sort() 是高度优化的 Timsort，对于几千几万的数据量，直接排序写起来更爽，可读性也无敌。

2. 边界条件处理

   注意我在取值前都加了 if len(...) >= 3。这一点很重要，因为题目没保证一定有足够的数。如果不加判断直接取下标 [0], [1], [2]，遇到短数组程序直接就崩了。

04. 还能优化吗？（给面试加分的点）

如果我们真的很较真（或者面试官问你能不能优化到 $O(N)$），其实是可以的。

仔细想想，我们真的需要把成千上万个数字都排序吗？

不需要。对于每个组，我们其实只关心最大的前 3 个数。

我们可以遍历一次数组，维护三个变量（比如max1, max2, max3）来记录每个分组的前三名。这样就不需要全排序，时间复杂度就能降到线性的 O(N)。

不过，在实际写业务逻辑或者一般的机试中，上面那版 $O(N \log N)$ 的代码因为逻辑简单、不易出错，反而是更好的选择。毕竟，先把代码写对，再考虑写快。

总结

这道题是典型的“模运算”应用。以后遇到“整除”、“倍数”之类的问题，别急着把数字加起来，先想想余数能不能帮你把问题简化。

把复杂问题拆解成几个小桶，分别处理，最后合并结果，这大概就是算法题带给我们解决问题的思路吧。