Tag

【哈希表】【数组】【2023-11-18】

---

题目来源

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

---

题目解读

在数组中找出数位和相等数对的和的最大值。

---

解题思路

方法一：哈希表

维护一个不同的数位和表示最大的数字的哈希表，我们可以先遍历数组 nums 填充哈希表，也可以一边遍历数组 nums 在哈希表中查找相应数位和的最大数字，一边更新哈希表。

实现代码

class Solution {
public:int maximumSum(vector<int>& nums) {unordered_map<int, int> mp; // 数位和：最大数字int res = -1;for (int num : nums) {int digitsSum = 0;int numCopy = num;while (numCopy) {digitsSum += numCopy % 10;numCopy /= 10;}if (mp[digitsSum]) {res = max(res, num + mp[digitsSum]);}mp[digitsSum] = max(mp[digitsSum], num);}return res;}
};

复杂度分析

时间复杂度：$O(nlogm)$，$n$ 为数组 nums 的长度，$m$ 为数组中 num 元素的最大值。

空间复杂度：$O(9\times logm)$。

---

写在最后

如果文章内容有任何错误或者您对文章有任何疑问，欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度方法，欢迎评论区交流。

最后，感谢您的阅读，如果感到有所收获的话可以给博主点一个 👍 哦。