LeetCode_ 2342_ Maximum sum of digits and equal pairs

Topic link

• https://leetcode.cn/problems/max-sum-of-a-pair-with-equal-sum-of-digits/

Title Description

I'll give you a subscript from 0 Starting array nums , The elements in the array are just Integers . Please choose two subscripts i and j（i != j）, And nums[i] The digits and And nums[j] The digit sum of is equal .

Please find all the subscripts that meet the conditions i and j , Find out and return to nums[i] + nums[j] What you can get Maximum .

Example 1：

 Input ：nums = [18,43,36,13,7]
 Output ：54
 explain ： Number pairs that meet the conditions  (i, j)  by ：

- (0, 2) , The digit sum of the two numbers is  9 , Add up to get  18 + 36 = 54 .
- (1, 4) , The digit sum of the two numbers is  7 , Add up to get  43 + 7 = 50 .
   So the maximum sum that can be obtained is  54 .

Example 2：

 Input ：nums = [10,12,19,14]
 Output ：-1
 explain ： There is no number pair that satisfies the condition , return  -1 .

Tips ：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109

Their thinking

• First, sort the array , Then write a function to get the sum of each digit of each integer
• The initial maximum value is -1, Traversal array , Use a hash table to record , Every time if the digit sum is updated , You can put it directly into the current nums[i], To ensure that what you put in and get is the largest

AC Code

class Solution {
    
    public int maximumSum(int[] nums) {
    
        Arrays.sort(nums);
        int ans = -1;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
    
            int k = getSum(nums[i]);
            if (map.containsKey(k)) {
    
                ans = Math.max(nums[i] + map.get(k), ans);
            }
            map.put(k, nums[i]);
        }
        return ans;
    }

    private static int getSum(int n) {
    
        int sum = 0;
        while (n > 0) {
    
            int tmp = n % 10;
            sum += tmp;
            n = n / 10;
        }
        return sum;
    }
}