網易首頁 > 網易號 > 正文申請入駐

2026-04-28：能被 3 整除的三元組最大和。用go語言，在數組 nums 中挑選出恰好三個數，使得這三個數的總和可以被 3 整除。要求計算所有

2026-04-28 00:09:54　來源: moonfdd

北京舉報

分享至

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

  

  

   


 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助力您的未來發展。

特別聲明：以上內容(如有圖片或視頻亦包括在內)為自媒體平臺“網易號”用戶上傳并發布，本平臺僅提供信息存儲服務。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.