刷题笔记(8):力扣-6164.数位和相等数对的最大和

本题来自 leetcode 题库第 209 题:6164.数位和相等数对的最大和。题目要求在所给的正整数数组中找到所有数位和相等的数对,并返回其中数对和最大的值。难度中等。

题目描述

给你一个下标从 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

题解

题目要求寻找所有数位和相同的数对中,两数之和最大的值。这就意味着需要先找到数位和相同的所有元素,然后再从中寻找和最大的值。最简单的思路便是双层循环遍历数组,对任意两两组合计算数位和,并判断是否相等,若相等则求和更新最大值。该算法时间复杂度为 \(O(n^2)\),空间复杂度为 \(O(1)\)

数位和

其中,要解决求数位和的问题。有两种思路,一种是使用现在高级语言一般都有的数字转字符串的接口,将数字转字符串,然后遍历字符求和。另一种是使用取余和取整的数学知识,循环获取各个数位并求和。具体的代码如下:

1
2
3
4
5
let sum = 0
while (num) {
sum += num % 10 // 获取个位数
num = Math.floor(num / 10) // 去掉个位数
}

也许使用转字符串的写法可以使代码更简洁,但第二种写法往往具有更高的性能,这一点在代码耗时中对比非常明显

分组

在暴力解法中,我们每次遍历时都要重新求解数位和,其中将造成大量重复工作。因此,我们考虑先计算每个元素的数位和,并使用 \(O(n)\) 的空间记录下结果。但此时算法的时间复杂度仍然是 \(O(n^2)\),这是因为我们遍历了任意可能的数对,而未考虑是否满足数位和相等。为了解决这个问题,我们可以在计算每个元素数位和时,使用哈希表来将数组分组,把所有数位和相等的元素分为一组。然后遍历这个哈希表,将每一组中的元素排序后取最大的两个元素相加更新最大值,即可。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* @param {number[]} nums
* @return {number}
*/
var maximumSum = function (nums) {
const map = new Map()
for (let num of nums) {
let d_sum = 0
let _num = num
while (_num > 0) {
d_sum += _num % 10
_num = Math.floor(_num / 10)
}
if (map.has(d_sum)) { map.get(d_sum).push(num) }
else map.set(d_sum, [num])
}
let ans = -1
for (let [k, v] of map) {
if (v.length < 2) continue
v.sort((a, b) => b - a)
ans = Math.max(ans, v[0] + v[1])
}
return ans
};

该算法时间复杂度不超过 \(O(n\log n)\),空间复杂度为 \(O(n)\)

维护最大的两个数

上面分组的改进使得我们将之前的双层循环改进成只需遍历一边分组哈希表即可,降低了复杂度。但注意到,遍历每个分组时,仍需进行排序操作,而我们要求的最大值只可能是分组数组中最大的两个数字和,而无需关心其他元素的大小顺序。因此,将所有元素排序座了额外的不必要工作。改为只查找最大的两个数即可,而最大的两个数可以在组织哈希表时维护,进一步降低复杂度。

遍历一个数组时,寻找最大值非常常见,那么如何寻找最大的前 2 个数呢?其实也非常简单,只需要额外的一个变量即可。具体的代码见下:

1
2
3
4
5
6
7
8
9
10
11
12
let max = 0
let max2 = 0
for (e of arr) {
if (e > max) {
// 找到比最大值大的数时,将最大值更新为该值,并将次大值更新为原来的最大值
max2 = max
max = e
} else if (e > max2) {
// 找到介于两者之间的数时,直接将其更新为次大值即可
max2 = e
}
}

对于查找最大(小)的前 n 个值思路也类似。

根据以上思路,该题的算法最终可优化为下:

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
/**
* @param {number[]} nums
* @return {number}
*/
var maximumSum = function (nums) {
const map = new Map()
for (let num of nums) {
let d_sum = 0
let _num = num
while (_num) {
d_sum += _num % 10
_num = Math.floor(_num / 10)
}
if (map.has(d_sum)) {
const v = map.get(d_sum)
if (num > v[0]) map.set(d_sum, [num, v[0]])
else if (num > v[1]) v[1] = num
} else map.set(d_sum, [num, 0])
}

let ans = -1
map.forEach(v => {
if (v[1] === 0) return
ans = Math.max(ans, v[0] + v[1])
})

return ans
};

该算法的时间复杂度为 \(O(n)\),空间复杂度为 \(O(n)\),但比上一种方法在执行耗时中节约了近一半时间!

总结与思考

这是一道周赛题,当时除了暴力解法没有想到更优的算法。该题需要注意几个技巧:

  1. 使用哈希表分组的思想,这样就能先做筛选,避免无效循环。

  2. 查找数组中最大的 2 个数的方法。

  3. 使用数学方法求数位和,效率更高!