2026-04-28：能被 3 整除的三元组最大和。用go语言，在数组 nums 中挑选出恰好三个数，使得这三个数的总和可以被 3 整除。 要求计算所有满足条件的三元组里，它们的三个数之和所能达到的最

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）。

2. 动态规划数组定义

创建二维数组f，格式：f[选了i个数][余数为r] = 最大和

• 第一维：0~3，代表当前选中的数字个数（0个、1个、2个、3个）；
• 第二维：0~2，代表当前数字总和对3取余的结果；
• 数组值：存储对应状态下的最大总和。

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)。

2. 额外空间复杂度

• 动态规划数组是固定大小：4行 × 3列 = 12个元素；
• 空间大小不随数组长度变化，是常数级空间；
• 额外空间复杂度：O(1)。

总结

1. 解题核心：用动态规划记录「选几个数+总和余数」的最大和，精准匹配「恰好3个数、能被3整除」的要求；
2. 处理逻辑：逐个遍历数字，更新所有可能的状态，只保留最大和；
3. 效率：时间O(n)（处理10万数据极快），空间O(1)（占用内存极小），完全满足题目数据规模要求。

Go完整代码如下：

packagemainimport("fmt""math")funcmaximumSum(nums[]int)int{constK=3constMOD=3f:=[K+1][MOD]int{}fori:=rangef{forj:=rangef[i]{f[i][j]=math.MinInt}}f[0][0]=0for_,x:=rangenums{forj:=K-1;j>=0;j--{forr:=rangeMOD{f[j+1][(r+x)%MOD]=max(f[j+1][(r+x)%MOD],f[j][r]+x)}}}returnmax(f[K][0],0)}funcmain(){nums:=[]int{4,2,3,1}result:=maximumSum(nums)fmt.Println(result)}

Python完整代码如下：

# -*-coding:utf-8-*-importmathdefmaximum_sum(nums):K=3MOD=3# 初始化 dp 表，dp[j][r] 表示选 j 个数，和模 MOD 为 r 的最大和dp=[[-math.inf]*MODfor_inrange(K+1)]dp[0][0]=0forxinnums:# 倒序更新 j，确保每个数最多选一次（0/1 背包）forjinrange(K-1,-1,-1):forrinrange(MOD):# 避免在更新过程中使用本轮已更新的值，倒序 j 已保证new_r=(r+x)%MODifdp[j][r]!=-math.inf:dp[j+1][new_r]=max(dp[j+1][new_r],dp[j][r]+x)# 返回选恰好 K 个数且和能被 MOD 整除的最大和，若不存在则返回 0returnmax(dp[K][0],0)if__name__=="__main__":nums=[4,2,3,1]result=maximum_sum(nums)print(result)

C++完整代码如下：

#include<iostream>#include<vector>#include<algorithm>#include<climits>usingnamespacestd;intmaximumSum(vector<int>&nums){constintK=3;constintMOD=3;// 初始化 dp 表，f[j][r] 表示选 j 个数，和模 MOD 为 r 的最大和vector<vector<int>>f(K+1,vector<int>(MOD,INT_MIN));f[0][0]=0;for(intx:nums){// 倒序更新 j，确保每个数只使用一次for(intj=K-1;j>=0;j--){for(intr=0;r<MOD;r++){if(f[j][r]!=INT_MIN){intnew_r=(r+x)%MOD;f[j+1][new_r]=max(f[j+1][new_r],f[j][r]+x);}}}}// 返回选恰好 K 个数且和能被 MOD 整除的最大和，若不存在则返回 0returnmax(f[K][0],0);}intmain(){vector<int>nums={4,2,3,1};intresult=maximumSum(nums);cout<<result<<endl;return0;}