难度: Medium
给你一个下标从 0 开始的数组 nums ，数组中的元素都是 正 整数。请你选出两个下标 i 和 j（i != j），且 nums[i] 的数位和 与 nums[j] 的数位和相等。
请你找出所有满足条件的下标 i 和 j ，找出并返回 nums[i] + nums[j] 可以得到的 最大值 。
示例 1：
输入：nums = [18,43,36,13,7] 输出：54 解释：满足条件的数对 (i, j) 为： - (0, 2) ，两个数字的数位和都是 9 ，相加得到 18 + 36 = 54 。 - (1, 4) ，两个数字的数位和都是 7 ，相加得到 43 + 7 = 50 。 所以可以获得的最大和是 54 。
示例 2：
输入：nums = [10,12,19,14] 输出：-1 解释：不存在满足条件的数对，返回 -1 。
提示：
1 <= nums.length <= 1051 <= nums[i] <= 109运行时间: 117 ms
内存: 30.5 MB
class Solution:
def maximumSum(self, nums: List[int]) -> int:
ans = 0
mx_dict = {}
nums.sort(reverse=True)
for num in nums:
if ans >= nums[0] + num:
break
cnt = sum(int(c) for c in str(num))
if cnt in mx_dict:
ans = max(ans, mx_dict[cnt] + num)
if num <= mx_dict[cnt]:
continue
mx_dict[cnt] = num
return ans if ans else -1
此题解采用哈希表来记录每个数位和对应的最大数字。首先，将数组按降序排序，这样可以优先处理较大的数值，从而有可能更早地找到最大的数对和。对于排序后的每个数字，计算其数位和，并在哈希表中查找是否已经存在相同数位和的数字。如果存在，则尝试更新最大和，即比较当前的最大和与这两个数字之和。此外，如果当前数字大于哈希表中记录的同数位和的最大值，则更新哈希表中的值。排序的目的是尽可能地获得最大的数对和，同时也利用排序的特性，在满足条件的最大和一旦找到后，可以提前终止循环，从而提高效率。
时间复杂度: O(n log n)
空间复杂度: O(1)
class Solution:
def maximumSum(self, nums: List[int]) -> int:
ans = 0 # 初始化最大和为0
mx_dict = {} # 哈希表记录数位和及其对应的最大数值
nums.sort(reverse=True) # 将数组降序排序
for num in nums:
if ans >= nums[0] + num:
break # 如果当前最大和已经达到可能的最大值，则终止循环
cnt = sum(int(c) for c in str(num)) # 计算当前数字的数位和
if cnt in mx_dict:
ans = max(ans, mx_dict[cnt] + num) # 更新最大和
if num <= mx_dict[cnt]:
continue # 如果当前数字不大于哈希表中的值，则跳过更新哈希表
mx_dict[cnt] = num # 更新哈希表中的最大数字
return ans if ans else -1 # 如果找到有效的最大和则返回，否则返回-1
在大多数编程问题中，尽管数字的位数d理论上与数字的大小成对数关系，但在实践中，这个位数通常远小于输入数组的长度。例如，即使是一个非常大的数如1000000，其位数也只有7，这相对于可能处理的数的总数（例如数以千计或更多）是很小的。因此，在分析算法的时间复杂度时，我们常常认为d是一个较小的常数。
这是一个优化和空间复杂度权衡的问题。如果存储每一个数位和对应的两个最大数值，虽然可以直接计算最大和，但这会增加空间复杂度和更新哈希表时的复杂性。每次更新哈希表时，都需要比较并可能更新两个数值，这使得代码复杂且容易出错。相比之下，只存储一个最大数值，并在遍历数组时更新最大和，可以保持代码的简洁性和高效性。
这里的逻辑基于数组已经被降序排序。因此，数组的第一个元素是最大的。在遍历过程中，如果已知的最大和大于或等于两个最大可能元素（即数组的第一个元素和当前遍历到的元素）的和，那么可以确信不会有更大的和出现，因为后续的元素只会更小。这是一种基于排序和当前已知最大值的贪心策略，用于尽早终止循环以提高效率。