难度: Easy
给你一个下标从 0 开始的整数数组 nums 。请你从 nums 中找出和 最大 的一对数，且这两个数数位上最大的数字相等。
返回最大和，如果不存在满足题意的数字对，返回 -1 。
示例 1：
输入：nums = [51,71,17,24,42] 输出：88 解释： i = 1 和 j = 2 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 71 + 17 = 88 。 i = 3 和 j = 4 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 24 + 42 = 66 。 可以证明不存在其他数对满足数位上最大的数字相等，所以答案是 88 。
示例 2：
输入：nums = [1,2,3,4] 输出：-1 解释：不存在数对满足数位上最大的数字相等。
提示：
2 <= nums.length <= 1001 <= nums[i] <= 104运行时间: 58 ms
内存: 16.0 MB
class Solution:
def maxSum(self, nums: List[int]) -> int:
d = defaultdict(list)
for x in nums:
d[max(str(x))].append(x)
return max((sum(sorted(v)[-2:]) for v in d.values() if len(v) >= 2), default=-1)
该题解采用哈希表的方法。首先，遍历数组nums，对于每个元素x，将其转换为字符串，然后找出其数位上的最大数字，将x添加到以该最大数字为键的哈希表d的对应列表中。这样，哈希表d的每个键对应的列表中都是数位上最大数字相同的元素。接着，遍历哈希表d的每个值（即列表），如果列表长度大于等于2，说明存在至少两个数位上最大数字相同的元素，计算这两个元素的和（取列表中最大的两个元素求和），并更新最大和。最后，返回最大和，如果不存在满足条件的数对，则返回-1。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def maxSum(self, nums: List[int]) -> int:
d = defaultdict(list) # 创建一个默认值为列表的哈希表
for x in nums: # 遍历数组
d[max(str(x))].append(x) # 将x添加到以其数位上最大数字为键的列表中
# 计算每个列表中最大的两个元素的和，并返回最大值，如果不存在，则返回-1
return max((sum(sorted(v)[-2:]) for v in d.values() if len(v) >= 2), default=-1)
从整数中找到数位上的最大数字，可以将整数转换为字符串，然后遍历字符串的每个字符，找出最大的字符。这种方法的时间复杂度为O(D)，其中D为数字的位数，通常D非常小（例如，对于大多数应用，D≤10）。因此，这种方法是高效的。尽管存在其他可能的方法，如逐位除以10并比较余数，但字符串方法的代码更简洁易懂，且在实际应用中效率也非常高。
该算法的目标是找到最大的数对和。在哈希表的每个列表中，最大的两个元素的和肯定是该列表可能的最大数对和。考虑其他元素组合的和只会产生更小的结果或相等的结果。因此，为了优化性能，无需考虑其他组合，直接取最大的两个元素求和即可达到找到最大数对和的目的。
如果数组中有多个相同的数字，这些数字在哈希表的同一个键下的列表中会出现多次。在计算最大的两个元素的和时，这种情况不会影响求和的正确性。即使这些相同的数字是列表中的最大值，只要列表长度至少为2，就可以正确计算出这两个相同数字的和。因此，这种情况下的处理不会影响求和的结果。
哈希表的键的数量m是由数组中元素的数位上最大数字决定的。因为数位上的数字只能是0到9，所以键的数量m最多为10，这通常小于数组长度n，特别是在处理大型数据集时。例如，考虑数组[12, 34, 56, 78, 90]，哈希表的键将是1, 3, 5, 7, 9，总共5个键，而数组长度为5，键的数量确实小于或等于数组长度。这一规律在大多数情况下都是成立的，除非数组非常小或每个数字都只有一个数位。