What is the time complexity of solving Max Sum of a Pair With Equal Sum of Digits?

The time complexity is O(n log m), where n is the array length and m is the value of the largest number in the array.

How do I calculate the sum of digits for large numbers in this problem?

You can calculate the sum of digits by repeatedly dividing the number by 10 and adding the remainders. This process takes O(log m) time, where m is the number itself.

How can I handle cases where no valid pair exists?

If no valid pair exists, the correct output is -1. Ensure your algorithm correctly handles this case by checking the hash table for valid pairs.

What is the best approach for handling large arrays in Max Sum of a Pair With Equal Sum of Digits?

Efficient array scanning combined with hash lookups ensures that the algorithm runs in linear time with respect to the array length, making it scalable for large inputs.

What is the pattern used in Max Sum of a Pair With Equal Sum of Digits?

The pattern involves array scanning combined with hash table lookup to track the maximum sum of numbers that share the same sum of digits.

#2342

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

数位和相等数对的最大和

给你一个下标从 0 开始的数组 nums ，数组中的元素都是正整数。请你选出两个下标 i 和 j （ i != j ），且 nums[i] 的数位和与 nums[j] 的数位和相等。请你找出所有满足条件的下标 i 和 j ，找出并返回 nums[i] + nums[j] 可以得到的最大值 …

数组哈希表排序堆（优先队列）

题目描述

给你一个下标从 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
解释：满足条件的数对 (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 <= 10⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：哈希表

我们可以用一个哈希表 $d$ 记录每个数位和对应的最大值，初始化一个答案变量 $ans = -1$ 。

接下来，我们遍历数组 $nums$ ，对于每个数 $v$ ，我们计算它的数位和 $x$ ，如果 $x$ 在哈希表 $d$ 中存在，那么我们就更新答案 $ans = \max(ans, d[x] + v)$ 。然后更新哈希表 $d[x] = \max(d[x], v)$ 。

最后返回答案 $ans$ 即可。

由于 $nums$ 中的元素最大为 $10^9$ ，因此数位和最大为 $9 \times 9 = 81$ ，我们可以直接定义一个长度为 $100$ 的数组 $d$ 来代替哈希表。

时间复杂度 $O(n \times \log M)$ ，空间复杂度 $O(D)$ ，其中 $n$ 是数组 $nums$ 的长度，而 $M$ 和 $D$ 分别是数组 $nums$ 中的元素的最大值和数位和的最大值。本题中 $M \leq 10^9$ ， $D \leq 81$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        d = defaultdict(int)
        ans = -1
        for v in nums:
            x, y = 0, v
            while y:
                x += y % 10
                y //= 10
            if x in d:
                ans = max(ans, d[x] + v)
            d[x] = max(d[x], v)
        return ans

speed

复杂度分析

指标	值
时间	O(n \log m)
空间	O(\log m)

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands the importance of efficient hashing.
question_mark
Candidate is familiar with digit manipulation and sum of digits calculation.
question_mark
Candidate recognizes the challenge of balancing time complexity with correctness.

warning

常见陷阱

外企场景

error
Not efficiently updating the hash table, leading to unnecessary re-checks.
error
Overlooking edge cases where no valid pairs exist, returning the correct -1 value.
error
Misunderstanding the sum of digits calculation and applying it incorrectly.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What happens if the array only has one number?
arrow_right_alt
How does the solution handle very large numbers or arrays at the upper constraint limits?
arrow_right_alt
Can we optimize this further if there are only a few numbers with unique digit sums?

help

常见问题

外企场景

继续练习

#2357 使数组中所有元素都等于零 #2402 会议室 III #2456 最流行的视频创作者