【LeetCode】统计一个数组中好对子的数目 Java 题解

2022 年 6 月 03 日
本文字数：1110 字
阅读完需：约 4 分钟

题目描述

给你一个数组 nums ，数组中只包含非负整数。定义 rev(x) 的值为将整数 x 各个数字位反转得到的结果。比方说 rev(123) = 321 ， rev(120) = 21 。我们称满足下面条件的下标对 (i, j) 是好的：

0 <= i < j < nums.lengthnums[i] + rev(nums[j]) == nums[j] + rev(nums[i])请你返回好下标对的数目。由于结果可能会很大，请将结果对 109 + 7 取余后返回。

示例 1：
输入：nums = [42,11,1,97]输出：2解释：两个坐标对为： - (0,3)：42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121 。 - (1,2)：11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12 。
示例 2：
输入：nums = [13,10,35,24,76]输出：4
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/count-nice-pairs-in-an-array著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是数组处理题目，题目要求是比较清晰的。第一步，需要实现反转函数。第二步，题目给出了判断下标的对数公式，然后我们可以根据公式做出判断，需要注意的是，这里的数值可能比较大，因此我们需要对答案进行取模操作。
具体第一步，反转函数，我们需要可以理解为取出数位重新计算。首先取出 num 的最高位，就是返回值的最低位，依次计算。
第二步，题目给出了计算公式。我们首先可以使用暴力的方式求解，这个题目的数据集比较大，无法通过所有测试用例。
我们再次分析这个公式 nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])。通过交换律，nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]) 。这样转换之后，是不是和我们的两数之和题目很像呢？我们使用 hashmap 记录每一个 nums[i] - rev(nums[i]) 的值，提升计算效率。实现代码如下，供参考。

通过代码

class Solution {    public int countNicePairs(int[] nums) {        int ans = 0;        int n = nums.length;        Map<Integer, Integer> map = new HashMap<>();        for (int num : nums) {            int temp = num - rev(num);            int cnt = map.getOrDefault(temp, 0);            ans += cnt;            ans %= 1000000007;            map.put(temp, cnt + 1);        }
        return ans;    }
    private int rev(int num) {        int ans = 0;        while (num > 0) {            ans = ans * 10 + num % 10;            num /= 10;        }        return ans;    }}