网站维护升级访问中,苏州seo安严博客,个人网站一键生成,网络推广方案七步法目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 描述#xff1a;
给你一个下…目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
https://github.com/September26/java-algorithms 原题链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 描述
给你一个下标从 0 开始的数组 nums 数组中的元素都是 正 整数。请你选出两个下标 i 和 ji ! 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 10^51 nums[i] 10^9 解题思路
这道题的数组长度范围是10^5所以时间复杂度应该是O(N)到O(N*lgN的级别。这道题是根据数位和来确定唯一的所以最合适的方式是使用哈希表的解题思路。
这题的核心其实是找到数位和一样并且累加值最大的那两个数。所以我们首先设置mMaxValue记录最大的两个数之和。因为我们只需要记录最大的那两个数所以没有必要使用List记录所有的因此使用NumModel记录数位和相同的所有数的状态其实也就是只记录最大的两个value1对应当前数组和最大的那个value2对应次大的。
遍历的过程中如果发现当前数组和所对应的数大于最大值则更新value1,value2,value。
如果当前数组和所对应的数大于次大值则更新value2和value。
最后返回maxValue即可。
代码 public class Solution2342 {int mMaxValue -1;public int maximumSum(int[] nums) {MapInteger, NumModel map new HashMap();for (int num : nums) {int key getKey(num);NumModel numModel map.get(key);if (numModel null) {numModel new NumModel();numModel.key key;numModel.value1 num;map.put(key, numModel);} else {insertModel(numModel, num);}}return mMaxValue;}private void insertModel(NumModel numModel, int num) {if (num numModel.value1) {numModel.value2 numModel.value1;numModel.value1 num;numModel.value numModel.value2 numModel.value1;mMaxValue Math.max(mMaxValue, numModel.value);return;}if (num numModel.value2) {numModel.value2 num;numModel.value numModel.value2 numModel.value1;mMaxValue Math.max(mMaxValue, numModel.value);}}private int getKey(int num) {int sum 0;while (num 0) {sum num % 10;num / 10;}return sum;}static class NumModel {int key 0;int value1 0;int value2 0;int value 0;}
}
