难度: Medium
给你一个整数数组 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^41 <= nums[i] <= 10^4运行时间: 41 ms
内存: 20.4 MB
class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
s = sum(nums)
if s % 3 == 0:
return s
a1 = sorted(x for x in nums if x % 3 == 1)
a2 = sorted(x for x in nums if x % 3 == 2)
if s % 3 == 2:
a1, a2 = a2, a1
ans = s - a1[0] if a1 else 0
if len(a2) > 1:
ans = max(ans, s - a2[0] - a2[1])
return ans
题解的思路主要包括先计算数组所有元素的总和，然后根据总和除以3的余数来调整元素选择，以确保能够获得能被3整除的最大和。首先，计算数组总和s。如果s能够被3整除，直接返回s作为结果。否则，根据s除3的余数（1或2），我们需要调整元素以使总和能被3整除。为此，将数组分成两组，一组的元素除以3余1，另一组除以3余2。如果总和除以3的余数为1，我们尝试移除一个余数为1的最小元素或两个余数为2的最小元素组合。反之，如果余数为2，我们尝试移除一个余数为2的最小元素或两个余数为1的最小元素组合。最终返回调整后的最大总和。
时间复杂度: O(n log n)
空间复杂度: O(n)
class Solution:
def maxSumDivThree(self, nums: List[int]) -> int:
s = sum(nums) # 计算数组所有元素的总和
if s % 3 == 0: # 如果总和可以被3整除，直接返回总和
return s
# 分别找出余数为1和2的元素列表
a1 = sorted(x for x in nums if x % 3 == 1)
a2 = sorted(x for x in nums if x % 3 == 2)
# 如果总和除以3的余数为2，则交换a1和a2
if s % 3 == 2:
a1, a2 = a2, a1
# 尝试移除一个余数为1的最小元素
ans = s - a1[0] if a1 else 0
# 尝试移除两个余数为2的最小元素，并取最大可能的和
if len(a2) > 1:
ans = max(ans, s - a2[0] - a2[1])
return ans
是的，这种选择策略是为了确保从总和中减去最小的可能值，以便使剩余值能被3整除。通过移除一个余数为1的最小元素或两个余数为2的最小元素，我们实际上是在尝试减去总和中最小的、能够改变总和余数的数值组合。这确保了我们从原始总和中减去的值尽可能小，从而使得剩余的和尽可能大。因此，这种策略通常能保证得到最大的可被三整除的和。
排序的目的是使得可以轻松地访问余数为1或2的最小元素，这对于实现上述移除策略是必要的。然而，排序一个列表的时间复杂度为O(n log n)，这可能不是最高效的方法。如果只需要找到最小的一个或两个元素，可以使用线性时间的选择算法，例如遍历数组并维护最小值或两个最小值，这样的时间复杂度为O(n)，比全数组排序更高效。
这里存在一个逻辑上的疏忽。即使数组中没有余数为1的元素，如果存在至少两个余数为2的元素，通过移除这两个余数为2的元素仍然可以得到一个非零的、可被三整除的最大和。因此，应该检查是否存在两个余数为2的元素，如果存在，则更新答案为 `s - a2[0] - a2[1]`，其中a2[0]和a2[1]是两个最小的余数为2的元素。只有当没有足够的元素来构成一个可以被移除的组合时，答案才应该是0。
在有多个相同的最小值的情况下，选择移除哪个具体的元素并不会影响最终的结果。因为这些元素的值相同，移除任何一个都会给总和带来相同的减少。因此，只要移除的是正确数量的最小值元素，具体选择哪个相同值的元素移除是没有影响的。