2026-04-28：能被 3 整除的三元组最大和。用go语言，在数组 nums 中挑选出恰好三个数，使得这三个数的总和可以被 3 整除。
要求计算所有满足条件的三元组里，它们的三个数之和所能达到的最大值；如果完全找不到满足条件的三元组，则结果为 0。
3 <= nums.length <= 100000。
1 <= nums[i] <= 100000。
输入: nums = [4,2,3,1]。
输出: 9。
解释:
总和能被 3 整除的有效三元组为：
(4, 2, 3)，和为 4 + 2 + 3 = 9。
(2, 3, 1)，和为 2 + 3 + 1 = 6。
因此，答案是 9。
题目来自力扣3779。
解题过程详细解析 一、核心定义与初始化准备 1. 关键常量定义
•
K=3：我们必须恰好选3个数字，这是固定要求；•
MOD=3：判断和能否被3整除，只需要看总和对3取余的结果（余数只能是0、1、2）。
创建二维数组f，格式：f[选了i个数][余数为r] = 最大和
• 第一维：
0~3，代表当前选中的数字个数（0个、1个、2个、3个）；• 第二维：
0~2，代表当前数字总和对3取余的结果；• 数组值：存储对应状态下的最大总和。
• 所有位置默认赋值为负无穷（表示初始状态不可达，没有有效数字）；
• 唯一初始有效状态：
f[0][0] = 0（选0个数，总和为0，余数0，和为0）。
遍历数组里的每一个数字x，从后往前更新动态规划数组（避免重复使用同一个数字），核心规则：
对于当前已选j个数字、余数为r的状态，加入数字x后，会变成：选j+1个数字、余数为(r+x)%3，总和变为 原总和 + x。
我们只保留每个状态下的最大总和。
分步处理示例（输入数组：[4,2,3,1]）
我们一步步看每个数字处理后，状态的变化：
1.处理第一个数字 4
• 4对3取余=1；
• 从选0个、余数0的状态，更新为：选1个、余数1，和为4；
• 此时有效状态：选1个余数1=4。
2.处理第二个数字 2
• 2对3取余=2；
• 基于选0个的状态：新增 选1个余数2=2；
• 基于选1个余数1的状态：新增 选2个余数0=4+2=6；
• 此时有效状态：选1个(1=4、2=2)，选2个(0=6)。
3.处理第三个数字 3
• 3对3取余=0；
• 基于选0个：新增 选1个余数0=3；
• 基于选1个：更新选2个的最大和（余数1=4+3=7、余数2=2+3=5）；
• 基于选2个余数0：更新选3个余数0=6+3=9（这就是最终答案）；
• 此时已经得到：恰好选3个数、余数0、和为9。
4.处理第四个数字 1
• 1对3取余=1；
• 继续更新所有状态，会得到另一个三元组和为6；
• 对比后，最大和依旧是9。
遍历结束后，我们只需要看一个目标状态：f[3][0]：恰好选3个数字，总和余数为0（能被3整除）的最大和。
• 如果这个值大于0，就返回它；
• 如果这个值无效（负无穷），说明没有符合条件的三元组，返回0。
示例中f[3][0]=9，所以最终输出9。
四、时间复杂度 & 额外空间复杂度 1. 时间复杂度
• 设数组长度为
n（最大10万）；• 动态规划的两层固定循环：选数字个数（3次）+ 余数（3次）= 固定9次操作；
• 总操作次数 =
n × 9，是线性复杂度；•时间复杂度：O(n)。
• 动态规划数组是固定大小：
4行 × 3列 = 12个元素；• 空间大小不随数组长度变化，是常数级空间；
•额外空间复杂度：O(1)。
1. 解题核心：用动态规划记录「选几个数+总和余数」的最大和，精准匹配「恰好3个数、能被3整除」的要求；
2. 处理逻辑：逐个遍历数字，更新所有可能的状态，只保留最大和；
3. 效率：时间O(n)（处理10万数据极快），空间O(1)（占用内存极小），完全满足题目数据规模要求。
package main
import (
"fmt"
"math"
)
func maximumSum(nums []int)int {
const K = 3
const MOD = 3
f := [K + 1][MOD]int{}
for i := range f {
for j := range f[i] {
f[i][j] = math.MinInt
}
}
f[0][0] = 0
for _, x := range nums {
for j := K - 1; j >= 0; j-- {
for r := range MOD {
f[j+1][(r+x)%MOD] = max(f[j+1][(r+x)%MOD], f[j][r]+x)
}
}
}
return max(f[K][0], 0)
}func main() {
nums := []int{4, 2, 3, 1}
result := maximumSum(nums)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
import math
def maximum_sum(nums):
K = 3
MOD = 3
# 初始化 dp 表，dp[j][r] 表示选 j 个数，和模 MOD 为 r 的最大和
dp = [[-math.inf] * MOD for _ in range(K + 1)]
dp[0][0] = 0
for x in nums:
# 倒序更新 j，确保每个数最多选一次（0/1 背包）
for j in range(K - 1, -1, -1):
for r in range(MOD):
# 避免在更新过程中使用本轮已更新的值，倒序 j 已保证
new_r = (r + x) % MOD
if dp[j][r] != -math.inf:
dp[j + 1][new_r] = max(dp[j + 1][new_r], dp[j][r] + x)
# 返回选恰好 K 个数且和能被 MOD 整除的最大和，若不存在则返回 0
return max(dp[K][0], 0)if __name__ == "__main__":
nums = [4, 2, 3, 1]
result = maximum_sum(nums)
print(result)
C++完整代码如下：
using namespace std;
int maximumSum(vector& nums) {
constint K = 3;
constint MOD = 3;// 初始化 dp 表，f[j][r] 表示选 j 个数，和模 MOD 为 r 的最大和
vector int >> f(K + 1 , vector< int >(MOD, INT_MIN));
f[ 0 ][ 0 ] = 0 ;
for ( int x : nums) {
// 倒序更新 j，确保每个数只使用一次
for ( int j = K - 1 ; j >= 0 ; j--) {
for ( int r = 0 ; r < MOD; r++) {
if (f[j][r] != INT_MIN) {
int new_r = (r + x) % MOD;
f[j + 1 ][new_r] = max(f[j + 1 ][new_r], f[j][r] + x);
}
}
}
}
// 返回选恰好 K 个数且和能被 MOD 整除的最大和，若不存在则返回 0
return max(f[K][ 0 ], 0 );
}
int main() {
vector< int > nums = { 4 , 2 , 3 , 1 };
int result = maximumSum(nums);
cout << result << endl;
return 0 ;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
热门跟贴