数位和相等数对的最大和
难度:
标签:
题目描述
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 and j 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 <= 1051 <= nums[i] <= 109
代码结果
运行时间: 117 ms, 内存: 30.5 MB
/*
题目思路：
1. 使用流来遍历数组中的每个数字，计算每个数字的数位和。
2. 使用一个哈希表记录数位和相同的数字的最大值。
3. 再次遍历数组，找到与当前数字数位和相同的数字，计算其和的最大值。
4. 返回最大值，如果没有找到则返回 -1。
*/
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class MaxPairSumStream {
public static int maxPairSum(int[] nums) {
Map<Integer, Integer> digitSumMap = new HashMap<>();
return Arrays.stream(nums)
.map(num -> {
int sumOfDigits = getDigitSum(num);
int maxSum = digitSumMap.getOrDefault(sumOfDigits, 0) + num;
digitSumMap.put(sumOfDigits, Math.max(digitSumMap.getOrDefault(sumOfDigits, 0), num));
return maxSum;
})
.filter(sum -> sum > 0)
.max()
.orElse(-1);
}
// 计算数字的数位和
private static int getDigitSum(int num) {
return String.valueOf(num).chars().map(c -> c - '0').sum();
}
public static void main(String[] args) {
int[] nums1 = {18, 43, 36, 13, 7};
int[] nums2 = {10, 12, 19, 14};
System.out.println(maxPairSum(nums1)); // 输出 54
System.out.println(maxPairSum(nums2)); // 输出 -1
}
}
解释
方法:
此题解采用哈希表来记录每个数位和对应的最大数字。首先，将数组按降序排序，这样可以优先处理较大的数值，从而有可能更早地找到最大的数对和。对于排序后的每个数字，计算其数位和，并在哈希表中查找是否已经存在相同数位和的数字。如果存在，则尝试更新最大和，即比较当前的最大和与这两个数字之和。此外，如果当前数字大于哈希表中记录的同数位和的最大值，则更新哈希表中的值。排序的目的是尽可能地获得最大的数对和，同时也利用排序的特性，在满足条件的最大和一旦找到后，可以提前终止循环，从而提高效率。
时间复杂度:
O(n log n)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么在计算数位和的时候，可以认为数字的位数d是一个常数，而不是随着输入nums的大小变化？
▷🦆
在哈希表中存储的是数位和对应的最大数值，为什么不考虑存储两个最大的数值以便直接计算最大和？
▷🦆
题解中提到如果当前最大和已经达到可能的最大值，则终止循环。如何确定已经达到可能的最大值，这里的逻辑是什么？
▷