日期: 2025 年 11 月 23 日

目标

给你一个整数数组 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 整除。

• 如果和 sum % 3 == 1，可以去掉一个模 3 余 1 的最小元素，或者 两个模 3 余 2 的最小元素
• 如果和 sum % 3 == 2，可以去掉一个模 3 余 2 的最小元素，或者 两个模 3 余 1 的最小元素

代码

/**
 * @date 2025-11-23 20:46
 */
public class MaxSumDivThree1262 {

    public int maxSumDivThree(int[] nums) {
        int res = 0;
        PriorityQueue<Integer> q1 = new PriorityQueue<>();
        PriorityQueue<Integer> q2 = new PriorityQueue<>();
        for (int num : nums) {
            res += num;
            if (num % 3 == 1) {
                q1.offer(num);
            } else if (num % 3 == 2) {
                q2.offer(num);
            }
        }
        int mod = res % 3;
        if (mod == 1) {
            int sub = q1.size() == 0 ? 100000 : q1.peek();
            if (q2.size() > 1) {
                sub = Math.min(sub, q2.poll() + q2.poll());
            }
            res -= sub;
        } else if (mod == 2) {
            int sub = q2.size() == 0 ? 100000 : q2.peek();
            if (q1.size() > 1) {
                sub = Math.min(sub, q1.poll() + q1.poll());
            }
            res -= sub;
        }
        return res;
    }
}

性能