Medium

题目描述

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

请你找出所有满足条件的下标对 (i, j) 中，nums[i] + nums[j] 的 最大值 ，并返回这个最大值。如果不存在满足条件的下标对，返回 -1 。

示例 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

解题思路

解题思路

这道题的核心思想是按数位和分组，然后在每个组内找出最大的两个数。

方法一：哈希表 + 排序（推荐）

  1. 计算数位和：遍历数组，为每个数字计算其数位和
  2. 分组存储：使用哈希表，以数位和为键，存储具有相同数位和的所有数字
  3. 找最大值对：对于每个组，如果组内元素个数 ≥ 2，则对该组排序，取最大的两个数相加

方法二：哈希表 + 维护最大两值

优化空间复杂度，对于每个数位和，只维护最大的两个值，避免存储所有元素。

方法三：堆

使用最大堆来维护每个数位和对应的最大两个元素。

时间复杂度主要来自于计算数位和 O(n×log(max_num)) 和可能的排序 O(n×log(n))，空间复杂度为 O(n)。

数位和的范围很小（最大为 9×10 = 90），所以实际运行效率很高。

代码实现

class Solution {
public:
    int maximumSum(vector<int>& nums) {
        unordered_map<int, vector<int>> groups;
        
        // 计算数位和并分组
        for (int num : nums) {
            int digitSum = getDigitSum(num);
            groups[digitSum].push_back(num);
        }
        
        int maxSum = -1;
        
        // 对每个组找最大的两个数
        for (auto& [digitSum, group] : groups) {
            if (group.size() >= 2) {
                sort(group.rbegin(), group.rend()); // 降序排序
                maxSum = max(maxSum, group[0] + group[1]);
            }
        }
        
        return maxSum;
    }
    
private:
    int getDigitSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
};

class Solution:
    def maximumSum(self, nums: List[int]) -> int:
        def get_digit_sum(num):
            return sum(int(digit) for digit in str(num))
        
        groups = {}
        
        # 计算数位和并分组
        for num in nums:
            digit_sum = get_digit_sum(num)
            if digit_sum not in groups:
                groups[digit_sum] = []
            groups[digit_sum].append(num)
        
        max_sum = -1
        
        # 对每个组找最大的两个数
        for group in groups.values():
            if len(group) >= 2:
                group.sort(reverse=True)
                max_sum = max(max_sum, group[0] + group[1])
        
        return max_sum

public class Solution {
    public int MaximumSum(int[] nums) {
        Dictionary<int, List<int>> groups = new Dictionary<int, List<int>>();
        
        // 计算数位和并分组
        foreach (int num in nums) {
            int digitSum = GetDigitSum(num);
            if (!groups.ContainsKey(digitSum)) {
                groups[digitSum] = new List<int>();
            }
            groups[digitSum].Add(num);
        }
        
        int maxSum = -1;
        
        // 对每个组找最大的两个数
        foreach (var group in groups.Values) {
            if (group.Count >= 2) {
                group.Sort((a, b) => b.CompareTo(a)); // 降序排序
                maxSum = Math.Max(maxSum, group[0] + group[1]);
            }
        }
        
        return maxSum;
    }
    
    private int GetDigitSum(int num) {
        int sum = 0;
        while (num > 0) {
            sum += num % 10;
            num /= 10;
        }
        return sum;
    }
}

var maximumSum = function(nums) {
    function getDigitSum(num) {
        let sum = 0;
        while (num > 0) {
            sum += num % 10;
            num = Math.floor(num / 10);
        }
        return sum;
    }
    
    const groups = new Map();
    
    // 计算数位和并分组
    for (const num of nums) {
        const digitSum = getDigitSum(num);
        if (!groups.has(digitSum)) {
            groups.set(digitSum, []);
        }
        groups.get(digitSum).push(num);
    }
    
    let maxSum = -1;
    
    // 对每个组找最大的两个数
    for (const group of groups.values()) {
        if (group.length >= 2) {
            group.sort((a, b) => b - a); // 降序排序
            maxSum = Math.max(maxSum, group[0] + group[1]);
        }
    }
    
    return maxSum;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × log(max_num) + k × m × log(m))n为数组长度，max_num为最大数字，k为不同数位和的个数，m为每组的平均大小
空间复杂度O(n)哈希表存储所有数字