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

福大大架构师每日一题

发布于 2026-04-28 19:49:13

620

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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完整代码如下：

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++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

int maximumSum(vector<int>& nums) {
    constint K = 3;
    constint MOD = 3;

    // 初始化 dp 表，f[j][r] 表示选 j 个数，和模 MOD 为 r 的最大和
    vector<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;
    return0;
}