今日问题

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

直觉思路

针对这个问题，我们可以模拟题目描述中的步骤，从而得到答案。

方法步骤

  1. 首先编写一个计数函数，用于计算所有整数的总和。
  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