2342. 数位和相等数对的最大和

🎯 问题描述（来源于LeetCode）

描述：
给你一个下标从 0 开始的数组 nums ，数组中的元素都是正整数。
请你选出两个下标 i 和 j（i != j），且 nums[i] 的数位和与 nums[j] 的数位和相等。
请你找出所有满足条件的下标 i 和 j ，找出并返回 nums[i] + nums[j] 可以得到的 最大值_。_如果不存在这样的下标对，返回 -1。

说明：

这是一个哈希表结合贪心算法的问题。
核心逻辑是将数字按照“数位和”进行分组。
对于同一个数位和组内的数字，为了使两数之和最大，我们只需要保留该组中最大的两个数（或者遍历时维护当前遇到的最大值）。
示例：
示例 1：

输入：nums = [18,43,36,13,7]
输出：54
解释：
- 数位和为 9 的数有：18 (1+8), 36 (3+6)。和为 18+36=54。
- 数位和为 7 的数有：43 (4+3), 7 (7)。和为 43+7=50。
- 最大和为 54。

示例 2：

1
2
3

输入：nums = [10,12,19,14]
输出：-1
解释：没有两个数的数位和相等。

💻 解题思路

思路1：哈希表 + 贪心

思路1：代码实现

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        # 辅助函数：计算一个整数的数位和
        def sum_bit(n: int):
            sum_num = 0
            while n:
                sum_num += n % 10  # 取最后一位
                n //= 10           # 去掉最后一位
            return sum_num
        
        ans = -1
        # 哈希表：键为数位和，值为该数位和对应的最大数字
        num_count = defaultdict(int)
        
        for num in nums:
            sum_c = sum_bit(num)
            
            # 如果该数位和之前出现过，说明可以组成数对
            if sum_c in num_count:
                # 更新最大和：当前数字 + 之前该组最大的数字
                ans = max(ans, num_count[sum_c] + num)
                
                # 更新该数位和对应的最大数字（贪心：保留最大的以便后续匹配）
                num_count[sum_c] = max(num_count[sum_c], num)
            else:
                # 如果该数位和第一次出现，直接存入
                num_count[sum_c] = num
                
        return ans

思路1：📊 性能分析

时间复杂度： $O(N \times \log M)$ $O (N \times lo g M)$
- 其中 $N$ 是数组 nums 的长度， $M$ 是数组中数字的最大值。
- 遍历数组需要 $O(N)$ 。
- 每次计算数位和 sum_bit 需要 $O(\log_{10} M)$ 的时间（即数字的位数）。
- 哈希表操作平均为 $O(1)$ 。
- 总时间复杂度为 $O(N \log M)$ 。
空间复杂度： $O(N)$ $O (N)$
- 哈希表 num_count 在最坏情况下（所有数字数位和都不同）需要存储 $N$ 个键值对。

思考

数位和计算：
- sum_bit 函数通过取模 % 10 和整除 // 10 来逐位提取数字并求和。这是计算数位和的标准方法。
贪心策略：
- 我们要找的是和最大的数对。
- 对于具有相同数位和的一组数字，假设我们已经遍历了部分数字，并记录了其中的最大值 max_val。
- 当我们遇到一个新的数字 num（且数位和相同）时，num + max_val 一定是当前能组成的最大和。
- 因此，哈希表中只需要存储每个数位和对应的最大数字。
- 代码中的 num_count[sum_c] = max(num_count[sum_c], num) 正是体现了这一贪心思想。
逻辑流程：
- 遍历每个数字 num。
- 计算其数位和 sum_c。
- 检查 sum_c 是否在哈希表中：
  - 存在：说明之前遇到过数位和相同的数字。计算 num + 历史最大值，更新全局答案 ans。然后更新哈希表中的最大值为 max(历史最大值, num)。
  - 不存在：说明这是该数位和第一次出现，将 num 存入哈希表。
边界情况：
- 数组长度为 1：无法组成数对，ans 保持 -1，返回 -1。
- 所有数字数位和都不同：哈希表中每个键只对应一个值，if sum_c in num_count 始终为假（除了第一次），返回 -1。
- 有重复数字：逻辑依然正确，因为重复数字的数位和相同，且会被正确比较大小。