Medium

题目描述

给你一个整数数组 nums。

你的任务是从 nums 中恰好选择三个整数，使得它们的和能被三整除。

返回这样的三元组的最大可能和。如果不存在这样的三元组，返回 0。

示例 1：

输入：nums = [4,2,3,1]
输出：9
解释：
和能被 3 整除的有效三元组有：
- (4, 2, 3)，和为 4 + 2 + 3 = 9
- (2, 3, 1)，和为 2 + 3 + 1 = 6
因此，答案是 9。

示例 2：

输入：nums = [2,1,5]
输出：0
解释：
没有三元组的和能被 3 整除，所以答案是 0。

约束条件：

  • 3 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

解题思路

解题思路

这是一道关于数学性质和贪心算法的题目。关键在于理解三个数的和能被3整除的条件。

核心观察

根据模运算的性质，三个数的和能被3整除，当且仅当这三个数对3取模的结果之和能被3整除。设三个数分别为 a, b, c，它们对3取模的结果为 a%3, b%3, c%3，那么 (a+b+c)%3 = (a%3 + b%3 + c%3)%3。

有效组合

对于三个数的模值组合，只有以下四种情况能使和被3整除：

  1. (0, 0, 0) - 三个数都能被3整除
  2. (1, 1, 1) - 三个数模3都余1
  3. (2, 2, 2) - 三个数模3都余2
  4. (0, 1, 2) - 三个数分别模3余0、1、2

算法步骤

  1. 将数组按照对3取模的结果分成三组：mod0、mod1、mod2
  2. 对每组按降序排列，确保优先选择最大的数
  3. 对于每种有效组合，尝试选择对应组中的最大值：
    • 组合1：选择mod0中最大的3个数
    • 组合2：选择mod1中最大的3个数
    • 组合3：选择mod2中最大的3个数
    • 组合4：分别选择mod0、mod1、mod2中的最大数
  4. 返回所有可能组合中的最大和

这种方法的时间复杂度为O(n log n)，主要消耗在排序上；空间复杂度为O(n)，用于存储分组。

代码实现

class Solution {
public:
    int maximumSum(vector<int>& nums) {
        vector<int> mod0, mod1, mod2;
        
        for (int num : nums) {
            if (num % 3 == 0) mod0.push_back(num);
            else if (num % 3 == 1) mod1.push_back(num);
            else mod2.push_back(num);
        }
        
        sort(mod0.rbegin(), mod0.rend());
        sort(mod1.rbegin(), mod1.rend());
        sort(mod2.rbegin(), mod2.rend());
        
        int maxSum = 0;
        
        // Case 1: 0 + 0 + 0
        if (mod0.size() >= 3) {
            maxSum = max(maxSum, mod0[0] + mod0[1] + mod0[2]);
        }
        
        // Case 2: 1 + 1 + 1
        if (mod1.size() >= 3) {
            maxSum = max(maxSum, mod1[0] + mod1[1] + mod1[2]);
        }
        
        // Case 3: 2 + 2 + 2
        if (mod2.size() >= 3) {
            maxSum = max(maxSum, mod2[0] + mod2[1] + mod2[2]);
        }
        
        // Case 4: 0 + 1 + 2
        if (!mod0.empty() && !mod1.empty() && !mod2.empty()) {
            maxSum = max(maxSum, mod0[0] + mod1[0] + mod2[0]);
        }
        
        return maxSum;
    }
};

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        mod0, mod1, mod2 = [], [], []
        
        for num in nums:
            if num % 3 == 0:
                mod0.append(num)
            elif num % 3 == 1:
                mod1.append(num)
            else:
                mod2.append(num)
        
        mod0.sort(reverse=True)
        mod1.sort(reverse=True)
        mod2.sort(reverse=True)
        
        max_sum = 0
        
        # Case 1: 0 + 0 + 0
        if len(mod0) >= 3:
            max_sum = max(max_sum, mod0[0] + mod0[1] + mod0[2])
        
        # Case 2: 1 + 1 + 1
        if len(mod1) >= 3:
            max_sum = max(max_sum, mod1[0] + mod1[1] + mod1[2])
        
        # Case 3: 2 + 2 + 2
        if len(mod2) >= 3:
            max_sum = max(max_sum, mod2[0] + mod2[1] + mod2[2])
        
        # Case 4: 0 + 1 + 2
        if mod0 and mod1 and mod2:
            max_sum = max(max_sum, mod0[0] + mod1[0] + mod2[0])
        
        return max_sum

public class Solution {
    public int MaximumSum(int[] nums) {
        List<int> mod0 = new List<int>();
        List<int> mod1 = new List<int>();
        List<int> mod2 = new List<int>();
        
        foreach (int num in nums) {
            if (num % 3 == 0) mod0.Add(num);
            else if (num % 3 == 1) mod1.Add(num);
            else mod2.Add(num);
        }
        
        mod0.Sort((a, b) => b.CompareTo(a));
        mod1.Sort((a, b) => b.CompareTo(a));
        mod2.Sort((a, b) => b.CompareTo(a));
        
        int maxSum = 0;
        
        // Case 1: 0 + 0 + 0
        if (mod0.Count >= 3) {
            maxSum = Math.Max(maxSum, mod0[0] + mod0[1] + mod0[2]);
        }
        
        // Case 2: 1 + 1 + 1
        if (mod1.Count >= 3) {
            maxSum = Math.Max(maxSum, mod1[0] + mod1[1] + mod1[2]);
        }
        
        // Case 3: 2 + 2 + 2
        if (mod2.Count >= 3) {
            maxSum = Math.Max(maxSum, mod2[0] + mod2[1] + mod2[2]);
        }
        
        // Case 4: 0 + 1 + 2
        if (mod0.Count > 0 && mod1.Count > 0 && mod2.Count > 0) {
            maxSum = Math.Max(maxSum, mod0[0] + mod1[0] + mod2[0]);
        }
        
        return maxSum;
    }
}

var maximumSum = function(nums) {
    const mod0 = [], mod1 = [], mod2 = [];
    
    for (let num of nums) {
        if (num % 3 === 0) mod0.push(num);
        else if (num % 3 === 1) mod1.push(num);
        else mod2.push(num);
    }
    
    mod0.sort((a, b) => b - a);
    mod1.sort((a, b) => b - a);
    mod2.sort((a, b) => b - a);
    
    let maxSum = 0;
    
    // Case 1: three numbers from mod0
    if (mod0.length >= 3) {
        maxSum = Math.max(maxSum, mod0[0] + mod0[1] + mod0[2]);
    }
    
    // Case 2: one from mod0, one from mod1, one from mod2
    if (mod0.length >= 1 && mod1.length >= 1 && mod2.length >= 1) {
        maxSum = Math.max(maxSum, mod0[0] + mod1[0] + mod2[0]);
    }
    
    // Case 3: three from mod1
    if (mod1.length >= 3) {
        maxSum = Math.max(maxSum, mod1[0] + mod1[1] + mod1[2]);
    }
    
    // Case 4: three from mod2
    if (mod2.length >= 3) {
        maxSum = Math.max(maxSum, mod2[0] + mod2[1] + mod2[2]);
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n log n)
空间复杂度O(n)

说明：

  • 时间复杂度：O(n log n)，主要消耗在对三个分组数组进行排序
  • 空间复杂度：O(n)，用于存储按模值分组的三个数组