class Solution {
public:
int maximumSum(vector<int>& nums) {
}
};
2342. 数位和相等数对的最大和
给你一个下标从 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 <= 1051 <= nums[i] <= 109原站题解
cpp 解法, 执行用时: 132 ms, 内存消耗: 58.9 MB, 提交时间: 2023-11-18 04:47:14
class Solution {
public:
int maximumSum(vector<int>& nums) {
int n = nums.size();
// 数位和，最大值
unordered_map<int, int> cnt;
int res = -1;
for(int i = 0; i < n; i++) {
// 当前值
int x = nums[i];
// 数位和
int cur = 0;
while(x > 0) {
cur += x % 10;
x /= 10;
}
if(cnt.count(cur)) {
res = max(res, nums[i] + cnt[cur]);
}
cnt[cur] = max(nums[i], cnt[cur]);
}
return res;
}
};
java 解法, 执行用时: 74 ms, 内存消耗: 58.1 MB, 提交时间: 2023-11-18 04:46:10
class Solution {
public int maximumSum(int[] nums) {
Arrays.sort(nums);
Map<Integer, Integer> map = new HashMap<>();
int res = -1;
for (int num : nums) {
int k = getSum(num);
if (map.containsKey(k)) {
res = Math.max(map.get(k) + num, res);
}
map.put(k, num);
}
return res;
}
int getSum(int i) {
int sum = 0;
while(i > 0) {
sum += i % 10;
i /= 10;
}
return sum;
}
}
golang 解法, 执行用时: 112 ms, 内存消耗: 9.7 MB, 提交时间: 2023-01-11 09:53:12
func maximumSum(nums []int) int {
ans := -1
mx := map[int]int{}
for _, v := range nums {
s := 0
for x := v; x > 0; x /= 10 {
s += x % 10
}
if mx[s] > 0 {
ans = max(ans, mx[s] + v)
}
mx[s] = max(mx[s], v)
}
return ans
}
func max(a, b int) int { if b > a { return b }; return a }
python3 解法, 执行用时: 440 ms, 内存消耗: 26.3 MB, 提交时间: 2023-01-11 09:52:52
class Solution:
def maximumSum(self, nums: List[int]) -> int:
ans = -1
mx = defaultdict(int)
for num in nums:
# s = sum(int(d) for d in str(num))
s, x = 0, num
while x:
s += x % 10
x //= 10
if s in mx: ans = max(ans, mx[s] + num)
mx[s] = max(mx[s], num)
return ans