今日题目

https://leetcode.com/problems/max-sum-of-a-pair-with-equal-sum-of-digits/description

思路

本题可以直接模拟题目描述的过程，从而得出答案。

方法

  1. 首先编写一个 count 函数，计算每个整数的各位数字之和。
  2. 使用字典存储每个数字和对应的最大两个值。
  3. 将当前数字与字典中已存储的两个数进行比较。
  4. 更新答案 ans（初始化为 -1），注意只有当字典中存在至少两个数时，才能更新答案。

复杂度

  • 时间复杂度：$O(Nlog(M))$，N 为序列长度，M 为最大数值。

  • 空间复杂度：$O(N)$。

代码

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        def cnt(x):
            res = 0
            while(x > 0):
                res += x % 10
                x //= 10
            return res

        dic = dict()
        ans = -1
        for x in nums:
            nx = cnt(x)
            if nx in dic:
                if x > dic[nx][0]:
                    dic[nx][1] = dic[nx][0]
                    dic[nx][0] = x
                    if dic[nx][1] > 0:
                        ans = max(ans, dic[nx][0] + dic[nx][1])
                elif x > dic[nx][1]:
                    dic[nx][1] = x
                    ans = max(ans, dic[nx][0] + dic[nx][1])
        
            else:
                dic.update({nx: [x, 0]})
        return ans

image.png