力扣每日一题2023.1.17---1814. 统计一个数组中好对子的数目

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

提示：
    1 <= nums.length <= 105
    0 <= nums[i] <= 109
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/count-nice-pairs-in-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

看见题目，先直接来个暴力，代码如下：

class Solution {
    public int countNicePairs(int[] nums) {
        int MOD = 1000000007;
        int[] rev = new int[nums.length];
        for (int i = 0; i < nums.length; i ++) {
            rev[i] = rev(nums[i]);
        }
        long res = 0;
        for (int i = 0; i < nums.length - 1; i ++) {
            for (int j = i + 1; j < nums.length; j ++) {
                if (nums[i] + rev[j] == rev[i] + nums[j]) {
                    res ++;
                }
            }
        }
        return (int)res % MOD;
    }
    private int rev (int num) {
        int ans = 0;
        while (num > 0) {
            ans = ans * 10 + num % 10;
            num /= 10;
        }
        return ans;
    }
}

果然超出时间限制，那么着手优化试试。

由于是查找，可以很容易就想到利用哈希表来降低时间复杂度。

代码如下：

class Solution {
    public int countNicePairs(int[] nums) {
        final int MOD = 1000000007;
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            int rev = 0;
            int tem = num;
            while (tem != 0) {
                rev = rev * 10 + tem % 10;
                tem /= 10;
            }
            if (map.containsKey(rev - num)) {
                int val = map.get(rev - num);
//                res只能用int，如果先用long，再在最后进行取余的话，会在最后几个测试用例和答案结果不一致，所以放中间就进行取余。
                res = (res + val) % MOD;
//                对相同值出现次数进行统计，如果题目要求的是彼此不同的好对子个数，可以将map直接优化成set。
                map.put(rev - num, val + 1);
            } else {
                map.put(rev - num, 1);
            }
        }
        return res % MOD;
    }
}

运行结果如下：

再查看官解，发现可以对代码进行进一步的优化：

具体思路和我写的相同，只不过是利用Map类的getOrDefault方法优化了containsKey判断和put更新的步骤。

class Solution {
    public int countNicePairs(int[] nums) {
        final int MOD = 1000000007;
        int res = 0;
        Map<Integer, Integer> h = new HashMap<Integer, Integer>();
        for (int i : nums) {
            int temp = i, j = 0;
            while (temp > 0) {
                j = j * 10 + temp % 10;
                temp /= 10;
            }
            res = (res + h.getOrDefault(i - j, 0)) % MOD;
            h.put(i - j, h.getOrDefault(i - j, 0) + 1);
        }
        return res;
    }
}


作者：LeetCode-Solution
链接：https://leetcode.cn/problems/count-nice-pairs-in-an-array/solution/tong-ji-yi-ge-shu-zu-zhong-hao-dui-zi-de-ywux/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

官解运行结果如下：