当前位置：首页 > news >正文

Leetcode-3780-Python

news 2026/3/26 14:29:37

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

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

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

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

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

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

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

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

余数党 0：比如 3, 0, 9, 12...
余数党 1：比如 1, 4, 7, 10...
余数党 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

代码复盘

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

为什么用列表而不是优先队列？
虽然用大顶堆（Priority Queue）看起来更“算法”一点，但在 Python 里，list.sort() 是高度优化的 Timsort，对于几千几万的数据量，直接排序写起来更爽，可读性也无敌。
边界条件处理
注意我在取值前都加了 if len(...) >= 3。这一点很重要，因为题目没保证一定有足够的数。如果不加判断直接取下标 [0], [1], [2]，遇到短数组程序直接就崩了。