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

🟠   🔖  数组 哈希表 排序 堆（优先队列）  🔗 力扣 LeetCode

题目

You are given a 0-indexed array nums consisting of positive integers. You can choose two indices i and j, such that i != j, and the sum of digits of the number nums[i] is equal to that of nums[j].

Return the maximum value of nums[i] + nums[j]that you can obtain over all possible indices i andj that satisfy the conditions.

Example 1:

Input: nums = [18,43,36,13,7]

Output: 54

Explanation: The pairs (i, j) that satisfy the conditions are:

• (0, 2), both numbers have a sum of digits equal to 9, and their sum is 18 + 36 = 54.
• (1, 4), both numbers have a sum of digits equal to 7, and their sum is 43 + 7 = 50.

So the maximum sum that we can obtain is 54.

Example 2:

Input: nums = [10,12,19,14]

Output: -1

Explanation: There are no two numbers that satisfy the conditions, so we return -1.

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

题目大意

给你一个下标从 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 <= 10^5
• 1 <= nums[i] <= 10^9

解题思路

1. 遍历 nums，计算每个数的数位和 sum
2. 用哈希表 map 记录每种数位和对应的最大数
   • 如果该 sum 已经在 map 中，则计算该值和当前数的和，并更新最大和：
     • 取出之前存储的最大值 another，计算 num + another，更新 max。
     • 如果 num 比 another 大，则替换 map[sum] = num。
   • 否则，直接存入 map[sum] = num。
3. 返回 max，若无匹配则返回 -1。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 nums 的长度，需要遍历 nums。
• 空间复杂度：O(n)，哈希表最坏情况下要记录 n 个数位和。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumSum = function (nums) {
	let max = -1; // 记录最大数对和
	let map = new Map(); // 记录每个数位和对应的最大数

	for (let num of nums) {
		// 计算 num 的数位和
		let temp = num,
			sum = 0;
		while (temp > 0) {
			sum += temp % 10;
			temp = Math.floor(temp / 10);
		}

		// 如果这个数位和已经存在，则尝试更新最大和
		if (map.has(sum)) {
			const another = map.get(sum);
			max = Math.max(max, num + another); // 计算当前最大和
			if (another < num) {
				map.set(sum, num); // 更新更大的数
			}
		} else {
			map.set(sum, num); // 存入初始最大值
		}
	}
	return max;
};