LeetCode 2342. 数位和相等数对的最大和：哈希表

【LetMeFly】2342.数位和相等数对的最大和：哈希表

力扣题目链接：https://leetcode.cn/problems/max-sum-of-a-pair-with-equal-sum-of-digits/

给你一个下标从 0 开始的数组 nums ，数组中的元素都是 正 整数。请你选出两个下标 i 和 j（i != j），且 nums[i] 的数位和 与  nums[j] 的数位和相等。

请你找出所有满足条件的下标 i 和 j ，找出并返回 nums[i] + nums[j] 可以得到的 最大值 。

 

示例 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 <= 105
• 1 <= nums[i] <= 109

方法一：哈希表

我们只需要建立一个哈希表，维护哈希表中“和为$key$的最大的两个数”即可。

具体怎么做呢？

遍历数组中的元素$t$，如果$t$的和在哈希表中，那么就保留“哈希表中”和“$t$”中较大的两个元素。

这里有一个小技巧：可以保持哈希表中的两个元素的相对顺序为第一个元素不小于第二个元素，这样替换时只需要比较$t$和哈希表对应元素的第二个元素即可。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(len(nums))$

AC代码

C++

inline int getSum(int n) {
    int ans = 0;
    while (n) {
        ans += n % 10;
        n /= 10;
    }
    return ans;
}

class Solution {
public:
    int maximumSum(vector<int>& nums) {
        unordered_map<int, pair<int, int>> ma;
        int ans = -1;
        for (int t : nums) {
            int s = getSum(t);
            if (t > ma[s].second) {
                ma[s].second = t;
            }
            if (ma[s].first < ma[s].second) {
                swap(ma[s].first, ma[s].second);
            }
            if (ma[s].second) {
                ans = max(ans, ma[s].first + ma[s].second);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Python

class Solution:
    def getSum(self, n: int) -> int:
        ans = 0
        while n:
            ans += n % 10
            n //= 10
        return ans
    
    def maximumSum(self, nums: List[int]) -> int:
        ans = -1
        ma = dict()
        for t in nums:
            s = self.getSum(t)
            if s in ma:
                if t > ma[s][1]:
                    ma[s][1] = t
                if ma[s][0] < ma[s][1]:
                    ma[s][0], ma[s][1] = ma[s][1], ma[s][0]
                ans = max(ans, sum(ma[s]))
            else:
                ma[s] = [t, 0]
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/134476645