题目描述
给你一个整数数组 nums
,请你找出并返回能被 3 整除的元素最大和。
样例
输入:nums = [3,6,5,1,8]
输出:18
解释:选出数字 3, 6, 1 和 8,它们的和是 18(可被 3 整除的最大和)。
输入:nums = [4]
输出:0
解释:4 不能被 3 整除,所以无法选出数字,返回 0。
输入:nums = [1,2,3,4,4]
输出:12
解释:选出数字 1, 3, 4 以及 4,它们的和是 12(可被 3 整除的最大和)。
限制
1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4
算法
(贪心,数学) $O(n)$
- 首先求出所有数字的和,求和过程中,记录下数字模 3 余 1 的最小值和次小值,以及模 3 余 2 的最小值和次小值。
- 如果求出的总和模 3 余 1,我们可以去掉一个模 3 余 1 的数字或者两个模 3 余 2 的数字,二者取最小去掉。
- 如果求出的总和模 3 余 2,我们可以去掉两个模 3 余 1 的数字或者一个模 3 余 2 的数字,二者取最小去掉。
- 如果求出的总和能被 3 整除,则直接返回。
时间复杂度
- 仅需遍历一次数组,故时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
int maxSumDivThree(vector<int>& nums) {
const int MAX = 100000;
int ans = 0;
int m1 = MAX, mn1 = MAX;
int m2 = MAX, mn2 = MAX;
for (int x: nums) {
ans += x;
if (x % 3 == 1) {
if (x < m1) {
mn1 = m1;
m1 = x;
} else if (x < mn1) {
mn1 = x;
}
} else if (x % 3 == 2) {
if (x < m2) {
mn2 = m2;
m2 = x;
} else if (x < mn2) {
mn2 = x;
}
}
}
if (ans % 3 == 1) return ans - min(m1, m2 + mn2);
if (ans % 3 == 2) return ans - min(m1 + mn1, m2);
return ans;
}
};