1262. 可被三整除的最大和 · ttttt

# 1262. 可被三整除的最大和 # 題目地址（1262. 可被三整除的最大和） <https://leetcode-cn.com/problems/greatest-sum-divisible-by-three/> ## 題目描述 ``` <pre class="calibre18">``` 給你一個整數數組 nums，請你找出并返回能被三整除的元素最大和。示例 1：輸入：nums = [3,6,5,1,8] 輸出：18 解釋：選出數字 3, 6, 1 和 8，它們的和是 18（可被 3 整除的最大和）。示例 2：輸入：nums = [4] 輸出：0 解釋：4 不能被 3 整除，所以無法選出數字，返回 0。示例 3：輸入：nums = [1,2,3,4,4] 輸出：12 解釋：選出數字 1, 3, 4 以及 4，它們的和是 12（可被 3 整除的最大和）。提示： 1 <= nums.length <= 4 * 10^4 1 <= nums[i] <= 10^4 ``` ``` ## 前置知識 - 數組 - 回溯法 - 排序 ## 暴力法 ## 公司 - 字節 - 網易有道 ### 思路一種方式是找出所有的能夠被 3 整除的子集，然后挑選出和最大的。由于我們選出了所有的子集，那么時間復雜度就是 O(2N)O(2^N)O(2N) ，毫無疑問會超時。這里我們使用回溯法找子集，如果不清楚回溯法，可以參考我之前的題解，很多題目都用到了，比如[78.subsets](https://github.com/azl397985856/leetcode/blob/master/problems/78.subsets.md)。更多回溯題目，可以訪問上方鏈接查看（可以使用一套模板搞定）： ![](https://img.kancloud.cn/9d/6d/9d6d207bb8d30dd37d5a0c1d8a5385e1_546x436.jpg) ### 代碼 ``` <pre class="calibre18">``` class Solution: def maxSumDivThree(self, nums: List[int]) -> int: self.res = 0 def backtrack(temp, start): total = sum(temp) if total % 3 == 0: self.res = max(self.res, total) for i in range(start, len(nums)): temp.append(nums[i]) backtrack(temp, i + 1) temp.pop(-1) backtrack([], 0) return self.res ``` ``` ## 減法 + 排序減法的核心思想是，我們求出總和。如果總和不滿足題意，我們嘗試減去最小的數，使之滿足題意。 ### 思路這種算法的思想，具體來說就是： - 我們將所有的數字加起來，我們不妨設為 total - total 除以 3，得到一個余數 mod， mod 可能值有 0，1，2. - 同時我們建立兩個數組，一個是余數為 1 的數組 one，一個是余數為 2 的數組 two - 如果 mod 為 0，我們直接返回即可。 - 如果 mod 為 1，我們可以減去 one 數組中最小的一個（如果有的話），或者減去兩個 two 數組中最小的（如果有的話），究竟減去誰取決誰更小。 - 如果 mod 為 2，我們可以減去 two 數組中最小的一個（如果有的話），或者減去兩個 one 數組中最小的（如果有的話），究竟減去誰取決誰更小。由于我們需要取 one 和 two 中最小的一個或者兩個，因此對數組 one 和 two 進行排序是可行的，如果基于排序的話，時間復雜度大致為 O(NlogN)O(NlogN)O(NlogN)，這種算法可以通過。以題目中的例 1 為例： ![](https://img.kancloud.cn/9f/68/9f6883bcfd8f1cd0abe16df4d20fdf94_1076x1186.jpg) 以題目中的例 2 為例： ![](https://img.kancloud.cn/41/0b/410bdccee9727f97add0134fc4b87025_1050x1186.jpg) ### 代碼 ``` <pre class="calibre18">``` class Solution: def maxSumDivThree(self, nums: List[int]) -> int: one = [] two = [] total = 0 for num in nums: total += num if num % 3 == 1: one.append(num) if num % 3 == 2: two.append(num) one.sort() two.sort() if total % 3 == 0: return total elif total % 3 == 1 and one: if len(two) >= 2 and one[0] > two[0] + two[1]: return total - two[0] - two[1] return total - one[0] elif total % 3 == 2 and two: if len(one) >= 2 and two[0] > one[0] + one[1]: return total - one[0] - one[1] return total - two[0] return 0 ``` ``` ## 減法 + 非排序 ### 思路上面的解法使用到了排序。我們其實觀察發現，我們只是用到了 one 和 two 的最小的兩個數。因此我們完全可以在線形的時間和常數的空間完成這個算法。我們只需要分別記錄 one 和 two 的最小值和次小值即可，在這里，我使用了兩個長度為 2 的數組來表示，第一項是最小值，第二項是次小值。 ### 代碼 ``` <pre class="calibre18">``` class Solution: def maxSumDivThree(self, nums: List[int]) -> int: one = [float('inf')] * 2 two = [float('inf')] * 2 total = 0 for num in nums: total += num if num % 3 == 1: if num < one[0]: t = one[0] one[0] = num one[1] = t elif num < one[1]: one[1] = num if num % 3 == 2: if num < two[0]: t = two[0] two[0] = num two[1] = t elif num < two[1]: two[1] = num if total % 3 == 0: return total elif total % 3 == 1 and one: if len(two) >= 2 and one[0] > two[0] + two[1]: return total - two[0] - two[1] return total - one[0] elif total % 3 == 2 and two: if len(one) >= 2 and two[0] > one[0] + one[1]: return total - one[0] - one[1] return total - two[0] return 0 ``` ``` ## 有限狀態機 ### 思路我在[數據結構與算法在前端領域的應用 - 第二篇](https://lucifer.ren/blog/2019/09/19/algorthimn-fe-2/) 中講到了有限狀態機。 ![](https://img.kancloud.cn/25/f4/25f450a97aa52a06a879f3d59bc15a2a_530x411.jpg) 狀態機表示若干個狀態以及在這些狀態之間的轉移和動作等行為的數學模型。通俗的描述狀態機就是定義了一套狀態変更的流程：狀態機包含一個狀態集合，定義當狀態機處于某一個狀態的時候它所能接收的事件以及可執行的行為，執行完成后，狀態機所處的狀態。狀態機使用非常廣泛，比如正則表達式的引擎，編譯器的詞法和語法分析，網絡協議，企業應用等很多領域都會用到。拿本題中來說，我們從左到右掃描數組的過程，將會不斷改變狀態機的狀態。我們使用 state 數組來表示本題的狀態： - state\[0\] 表示 mod 為 0 的最大和 - state\[1\] 表示 mod 為 1 的最大和 - state\[2\] 表示 mod 為 1 的最大和我們的狀態轉移方程就會很容易。說到狀態轉移方程，你可能會想到動態規劃。沒錯！這種思路可以直接翻譯成動態規劃，算法完全一樣。如果你看過我上面提到的文章，那么狀態轉移方程對你來說就會很容易。如果你不清楚，那么請往下看： - 我們從左往右不斷讀取數字，我們不妨設這個數字為 num。 - 如果 num % 3 為 0。那么我們的 state\[0\], state\[1\], state\[2\] 可以直接加上 num（題目限定了 num 為非負），因為任何數字加上 3 的倍數之后，mod 3 的值是不變的。 - 如果 num % 3 為 1。我們知道 state\[2\] + num 會變成一個能被三整除的數，但是這個數字不一定比當前的 state\[0\]大。代碼表示就是`max(state[2] + num, state[0])`。同理 state\[1\] 和 state\[2\] 的轉移邏輯類似。 - 同理 num % 3 為 2 也是類似的邏輯。 - 最后我們返回 state\[0\]即可。 ### 代碼 ``` <pre class="calibre18">``` class Solution: def maxSumDivThree(self, nums: List[int]) -> int: state = [0, float('-inf'), float('-inf')] for num in nums: if num % 3 == 0: state = [state[0] + num, state[1] + num, state[2] + num] if num % 3 == 1: a = max(state[2] + num, state[0]) b = max(state[0] + num, state[1]) c = max(state[1] + num, state[2]) state = [a, b, c] if num % 3 == 2: a = max(state[1] + num, state[0]) b = max(state[2] + num, state[1]) c = max(state[0] + num, state[2]) state = [a, b, c] return state[0] ``` ``` 當然這個代碼還可以簡化： ``` <pre class="calibre18">``` class Solution: def maxSumDivThree(self, nums: List[int]) -> int: state = [0, float('-inf'), float('-inf')] for num in nums: temp = [0] * 3 for i in range(3): temp[(i + num) % 3] = max(state[(i + num) % 3], state[i] + num) state = temp return state[0] ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) ## 關鍵點解析 - 貪婪法 - 狀態機 - 數學分析 ## 擴展實際上，我們可以采取加法（貪婪策略），感興趣的可以試一下。另外如果題目改成了`請你找出并返回能被x整除的元素最大和`，你只需要將我的解法中的 3 改成 x 即可。大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。目前已經 37K star 啦。大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。 ![](https://img.kancloud.cn/cf/0f/cf0fc0dd21e94b443dd8bca6cc15b34b_900x500.jpg)