每日一题-数位和相等数对的最大和

Posted on In

问题

Link

给你一个下标从 0 开始的数组 nums ，数组中的元素都是 正 整数。请你选出两个下标 i 和 j（i != j），且 nums[i] 的数位和 与 nums[j] 的数位和相等。

请你找出所有满足条件的下标 i 和 j ，找出并返回 nums[i] + nums[j] 可以得到的 最大值 。

思路

  1. 如图，进行一次遍历+更新最大值与哈希表的方式
  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
25
26
27
28
29
30
31
32
33
34
35
/**
 * @param {number[]} nums
 * @return {number}
 */
var maximumSum = function (nums) {
	const m = new Map();
	let result = -1;
	// loop
	for (let i = 0; i < nums.length; i++) {
		let sum = sumOfDigits(nums[i]);
		if (!m.has(sum)) {
			m.set(sum, nums[i]);
		} else {
			// update result
			result = Math.max(result, nums[i] + m.get(sum));
			// update hashmap
			m.set(sum, Math.max(m.get(sum), nums[i]));
		}
	}
	return result;
};

// get sum of digits
function sumOfDigits(n) {
	let strNum = Math.abs(n).toString();
	let digitSum = strNum.split("").reduce((sum, digit) => sum + parseInt(digit), 0);
	return digitSum;
}

console.log(
	maximumSum([
		229, 398, 269, 317, 420, 464, 491, 218, 439, 153, 482, 169, 411, 93, 147, 50, 347, 210, 251,
		366, 401,
	]),
);