【LeetCode】数位和相等数对的最大和 Java 题解
题目描述
给你一个下标从 0 开始的数组 nums ,数组中的元素都是 正 整数。请你选出两个下标 i 和 j(i != j),且 nums[i] 的数位和 与 nums[j] 的数位和相等。
请你找出所有满足条件的下标 i 和 j ,找出并返回 nums[i] + nums[j] 可以得到的 最大值 。
复制代码
思路分析
今天的算法题目是数组处理题目,题目首先需要找出满足数位和相等的 i, j。然后在求出 nums[i] + nums[j] 可以得到的 最大值。
数位和的定义就是数字每一位的元素相加,这是一个很经典的计算方法,熟记使用即可。快速判断数位和是否相等,我们使用 hashMap 的方式。记录每一个索引位置的数位。
由于加法的计算满足交换律。根据加法这个性质,我们可以先对整个 nums 数组进行排序。然后在计算 nums[i] + nums[j] 可以得到的 最大值的时候,就可以直接使用靠后的两个元素相加就可以。具体实现代码如下,供参考。
通过代码
复制代码
总结
上述算法的时间复杂度是 O(n * log n), 空间复杂度是 O(n)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【Albert】的原创文章。
原文链接:【http://xie.infoq.cn/article/69cfc56cddd99bf27912e1736】。文章转载请联系作者。
评论