【Leetcode合集】2342. 数位和相等数对的最大和

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

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

代码仓库地址： https://github.com/slience-me/Leetcode
个人博客 ：https://slienceme.xyz

给你一个下标从 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 。
1
2
3
4
5
6

示例 2：

输入：nums = [10,12,19,14]
输出：-1
解释：不存在满足条件的数对，返回 -1 。
1
2
3

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

方案1

class Solution {
public:
    int maximumSum(vector<int> &nums) {
        vector<int> sumVector; // 创建一个空的整数向量，记录数位和
        int maxNum = -1;
        for (const auto &item: nums) {
            int num = getSumOfNum(item);
            sumVector.push_back(num);
        }
        for(int i=0; i<sumVector.size(); i++){
            for(int j=i+1; j<sumVector.size(); j++){
                if(sumVector[i] == sumVector[j]){
                    if(nums[i]+nums[j]>maxNum){
                        maxNum = nums[i]+nums[j];
                    }
                }
            }
        }
        return maxNum;

    }

    int getSumOfNum(int num) {
        int sum = 0; // 12345
        while (num != 0) {
            sum += (num % 10);
            num /= 10;
        }
        return sum;
    }
};
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
30
31

超出时间限制

方案2

在给定的代码中，您的目标是找到满足数位和相等的两个数的和的最大值。目前的方法是使用两层嵌套的循环来检查所有数对，并找到它们的数位和相等的情况下的最大和。
有一些地方可以进行优化来提高算法的效率：

1. 使用哈希表存储数位和的索引： 可以使用哈希表（unordered_map）存储数位和及其对应的索引，这样可以在一次遍历中找到符合条件的数对。
2. . 不需要构建额外的向量存储数位和： 在遍历原始数组时，直接计算数位和并在哈希表中查找，而不需要额外的向量来存储数位和。

class Solution {
public:
    int maximumSum(vector<int> &nums) {
        unordered_map<int, vector<int>> sumIndexMap;
        int maxSum = -1;

        for (int num : nums) {
            int sum = getSumOfNum(num);
            sumIndexMap[sum].push_back(num);
        }
        for (auto& pair : sumIndexMap) {
            if (pair.second.size() >= 2) {
                sort(pair.second.rbegin(), pair.second.rend());
                maxSum = max(maxSum, pair.second[0] + pair.second[1]);
            }
        }
        return maxSum;

    }
    int getSumOfNum(int num) {

        if (num < 0) {
            return -1;
        }
        int sum = 0; // 12345
        while (num != 0) {
            sum += (num % 10);
            num /= 10;
        }
        return sum;
    }
};
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
30
31
32

执行用时分布 208ms 击败16.01%使用 C++ 的用户

消耗内存分布 65.10MB 击败19.74%使用 C++ 的用户

方案3

单次循环解决问题，不再多一步排序

class Solution {
public:
    int maximumSum(vector<int> &nums) {
        unordered_map<int, int> sumIndexMap; //存储数位和对应索引
        int maxSum = -1; // 最大值
        // 先全部放入哈希表
        for (int num: nums) {
            int sum = getSumOfNum(num);
            if (sumIndexMap.count(sum)) {
                maxSum = max(maxSum, sumIndexMap[sum] + num);
                sumIndexMap[sum] = max(sumIndexMap[sum], num);
            } else {
                sumIndexMap[sum] = num;
            }
        }
        return maxSum;

    }
    int getSumOfNum(int num) {

        if (num < 0) {
            return -1;
        }
        int sum = 0; // 12345
        while (num != 0) {
            sum += (num % 10);
            num /= 10;
        }
        return sum;
    }
};
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
30
31

执行用时分布 144ms 击败66.89%使用 C++ 的用户

消耗内存分布 57.78MB 击败39.91%使用 C++ 的用户

方案4

纯属组解决问题

class Solution {
public:
    int maximumSum(vector<int> &nums) {
        int maxArray[120]={0}; //先给够
        int maxSum = -1; // 最大值
        // 先全部放入哈希表
        for (int num: nums) {
            int sum = getSumOfNum(num);
            if (maxArray[sum]) {
                maxSum = max(maxSum, maxArray[sum] + num);
                maxArray[sum] = max(maxArray[sum], num);
            } else {
                maxArray[sum] = num;
            }
        }
        return maxSum;

    }
    int getSumOfNum(int num) {

        if (num < 0) {
            return -1;
        }
        int sum = 0; // 12345
        while (num != 0) {
            sum += (num % 10);
            num /= 10;
        }
        return sum;
    }
};
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
30
31

执行用时分布 208ms 击败16.01%使用 C++ 的用户

消耗内存分布 65.10MB 击败19.74%使用 C++ 的用户