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

我的解法：
对数组进行排序，最大数一定最先进入哈希表进行加和

class Solution {
public:
    int maximumSum(vector<int>& nums) {
        unordered_map<int, vector<int>> h;
        int ans = -1;
        sort(nums.begin(), nums.end());
        for (int i = nums.size() - 1; i >= 0; i--) {
            int num = nums[i];
            int sum = 0;
            while (num != 0) {
                sum += num % 10;
                num = num / 10;
            }
            h[sum].push_back(nums[i]);
            if (h[sum].size() >= 2) {
                ans = max(ans, h[sum][0] + h[sum][1]);
                continue;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

注意这里：

			if (h[sum].size() >= 2) {
                ans = max(ans, h[sum][0] + h[sum][1]);
                continue;
            }
1
2
3
4

我原来写成了：

			if (h[sum].size() >= 2) {
                ans = max(ans, h[sum][0] + h[sum][1]);
                break;
            }
1
2
3
4

这是不对的，不一定最先凑对的两个数字的加和最大。
例如：[51, 32, 91, 42, 71, 19]

优化：
由于1 <= nums[i] <= 1e9，所以每个数字对应的数位和最大值为9*9=81，于是初始化哈希表可以优化为大小为100的数组
在数组里存储遇到的最大num，当前数位和对应数字不为0时（即已有等于当前数位和的数字进入，可以确保保存当前数位和的最大数），则更新ans，其中“确保保存当前数位和的最大数”通过这句实现：

h[sum] = max(h[sum], num);
1

整体代码：

class Solution {
public:
    int maximumSum(vector<int>& nums) {
        vector<int> h(100, 0);
        int ans = -1;
        for (int num: nums) {
            int t = num;
            int sum = 0;
            while (t != 0) {
                sum += t % 10;
                t = t / 10;
            }
            if (h[sum] != 0) ans = max(ans, h[sum] + num);
            h[sum] = max(h[sum], num);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18