[Java/Python 3] Compute the sum of digits and then use HashMap
Use a HashMap to save the sum of the digits of each number as the hash value (key of the map) and store the corresponding numbers into a list (value of the map)
1. Use a HashMap to save the sum of the digits of each number as the hash value (key of the map) and store the corresponding numbers into a list (value of the map).\n2. Sort each list and find the max sum of the pairs.\n\n```java\n    public int maximumSum(int[] nums) {\n        Map<Integer, List<Integer>> map = new HashMap<>();\n        for (int n : nums) {\n            map.computeIfAbsent(digitSum(n), l -> new ArrayList<>()).add(n);\n        }\n        int max = -1;\n        for (List<Integer> l : map.values()) {\n            if (l.size() > 1) {\n                Collections.sort(l);\n                int sz = l.size();\n                max = Math.max(max, l.get(sz - 1) + l.get(sz - 2));\n            }\n        }\n        return max;\n    }\n    private int digitSum(int n) {\n        int ans = 0;\n        while (n > 0) {\n            ans += n % 10;\n            n /= 10;\n        }\n        return ans;\n    }\n```\n\n```python\n    def maximumSum(self, nums: List[int]) -> int:\n        \n        def digitSum(n: int) -> int:\n            s = 0\n            while n > 0:\n                n, r = divmod(n, 10)\n                s += r\n            return s\n\n        d = defaultdict(list)\n        for num in nums:\n            d[digitSum(num)].append(num)\n        mx = -1    \n        for l in d.values():\n            if len(l) > 1:\n                l.sort()    \n                mx = max(mx, l[-1] + l[-2])\n        return mx\n```\n\n**Analysis:**\n\nTime: `O(nlogn)`, space: `O(n)`, where `n = nums.length`.\n\n----\n\nIn fact, we do NOT have to store all numbers for each hash value, just keep `2` largest numbers. Hence, we can optimize the above code from time `O(nlogn)` to `O(n)`.\n\n```java\n    public int maximumSum(int[] nums) {\n        Map<Integer, List<Integer>> digitSumToNums = new HashMap<>();\n        for (int n : nums) {\n            int digitSum = digitSum(n);\n            digitSumToNums.computeIfAbsent(digitSum, l -> new ArrayList<>()).add(n);\n            Collections.sort(digitSumToNums.get(digitSum));\n            if (digitSumToNums.get(digitSum).size() > 2) {\n                digitSumToNums.get(digitSum).remove(0);\n            }\n        }\n        int max = -1;\n        for (List<Integer> l : digitSumToNums.values()) {\n            if (l.size() == 2) {\n                max = Math.max(max, l.get(0) + l.get(1));\n            }\n        }\n        return max;\n    }\n    private int digitSum(int n) {\n        int ans = 0;\n        while (n > 0) {\n            ans += n % 10;\n            n /= 10;\n        }\n        return ans;\n    }\n```\n```python\n    def maximumSum(self, nums: List[int]) -> int:\n        \n        def digitSum(n: int) -> int:\n            s = 0\n            while n > 0:\n                n, r = divmod(n, 10)\n                s += r\n            return s\n\n        digit_sum_to_nums = defaultdict(list)\n        for num in nums:\n            digit_sum = digitSum(num)\n            digit_sum_to_nums[digit_sum].append(num)\n            digit_sum_to_nums[digit_sum].sort(reverse=True)\n            if len(digit_sum_to_nums[digit_sum]) > 2:\n                digit_sum_to_nums[digit_sum].pop()\n            \n        mx = -1    \n        for l in digit_sum_to_nums.values():\n            if len(l) == 2:\n                mx = max(mx, sum(l))\n        return mx\n```\n\n**Analysis:**\n\nTime & space: `O(n)`, where `n = nums.length`.\n
[]