2815. 数组中的最大数对和 Easy

给你一个下标从 0 开始的整数数组 nums 。请你从 nums 中找出和 最大 的一对数，且这两个数数位上最大的数字相等。

返回最大和，如果不存在满足题意的数字对，返回 -1 。

示例 1：
输入：nums = [51,71,17,24,42]
输出：88
解释：
i = 1 和 j = 2 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 71 + 17 = 88 。
i = 3 和 j = 4 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 24 + 42 = 66 。
可以证明不存在其他数对满足数位上最大的数字相等，所以答案是 88 。

示例 2：
输入：nums = [1,2,3,4]
输出：-1
解释：不存在数对满足数位上最大的数字相等。

解题思路

输入：一个数组 nums

输出：找出和最大的一对数，并且这两个数要满足最大的数字相等，返回最大和

本题属于 数组排序 + 哈希表 问题。

我们可以先对数组排序再进行遍历，还需要用到一个哈希表记录之前记录的最大数字的下标

每次遍历都去哈希表找是否之前出现过相同的最大数字，找到则计算最大和

因为是排好序的数组所以往后找到的数字一定更大所以可以直接覆盖哈希表里的下标

代码实现

python

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        # 对输入数组进行升序排序，便于处理
        nums.sort()

        # 初始化字典，用于存储每个最大数字对应的索引
        cache = {}
        # 初始化最大和，设为-1（表示未找到有效结果）
        maxVal = -1

        # 遍历数组
        for i in range(len(nums)):
            # 初始化当前数字的最大位数
            maxD = 0
            # 获取当前数字
            num = nums[i]

            # 计算当前数字的最大位数
            while num:
                maxD = max(maxD, num % 10)  # 取最后一位与当前最大位数比较
                num = num // 10  # 移除最后一位
            
            # 如果当前最大位数已在缓存中，尝试更新最大和
            if maxD in cache:
                maxVal = max(nums[cache[maxD]] + nums[i], maxVal)
            
            # 更新缓存，记录当前最大位数的索引
            cache[maxD] = i
        
        # 返回最大和，如果没有找到有效组合则返回-1
        return maxVal

javascript

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSum = function(nums) {
    nums.sort((a, b) => a - b);

    let maxVal = -1;
    const cache = {};

    for (let i = 0; i < nums.length; i++) {
        let num = nums[i];

        let maxD = 0;
        while (num > 0) {
            maxD = Math.max(maxD, num % 10);
            num = Math.floor(num / 10);
        }

        if (maxD in cache) {
            maxVal = Math.max(maxVal, nums[cache[maxD]] + nums[i]);
        }

        cache[maxD] = i;
    }

    return maxVal;
};

复杂度分析

时间复杂度：O(n * logn)

空间复杂度：O(1)

链接

2815 国际版

2815 中文版