给你一个下标从 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 <= 105
1 <= nums[i] <= 109
class Solution:
def maximumSum(self, nums: List[int]) -> int:
d = defaultdict(list)
for i, v in enumerate(nums):
t = 0
while v:
t += v % 10
v //= 10
d[t].append(nums[i])
ans = -1
for v in d.values():
v.sort(reverse=True)
if len(v) > 1:
ans = max(ans, v[0] + v[1])
return ans
class Solution {
public int maximumSum(int[] nums) {
Map<Integer, List<Integer>> d = new HashMap<>();
for (int i = 0; i < nums.length; ++i) {
int v = nums[i];
int t = 0;
while (v != 0) {
t += v % 10;
v /= 10;
}
d.computeIfAbsent(t, k -> new ArrayList<>()).add(nums[i]);
}
int ans = -1;
for (List<Integer> v : d.values()) {
int n = v.size();
if (n > 1) {
Collections.sort(v);
ans = Math.max(ans, v.get(n - 1) + v.get(n - 2));
}
}
return ans;
}
}
class Solution {
public:
int maximumSum(vector<int>& nums) {
unordered_map<int, vector<int>> d;
for (int i = 0; i < nums.size(); ++i) {
int v = nums[i];
int t = 0;
while (v) {
t += v % 10;
v /= 10;
}
d[t].push_back(nums[i]);
}
int ans = -1;
for (auto& [_, v] : d) {
int n = v.size();
if (n > 1) {
sort(v.begin(), v.end());
ans = max(ans, v[n - 1] + v[n - 2]);
}
}
return ans;
}
};
func maximumSum(nums []int) int {
d := map[int][]int{}
for i, v := range nums {
t := 0
for v > 0 {
t += v % 10
v /= 10
}
d[t] = append(d[t], nums[i])
}
ans := -1
for _, v := range d {
n := len(v)
if n > 1 {
sort.Ints(v)
ans = max(ans, v[n-1]+v[n-2])
}
}
return ans
}
func max(a, b int) int {
if a > b {
return a
}
return b
}