Daily LeetCode – day0172 1814. Count Nice Pairs in an Array

import java.util.HashMap;
import java.util.Map;

// 1814. Count Nice Pairs in an Array
class Solution {
    public int countNicePairs(int[] nums) {
        Map<Integer, Integer> selfMinusReverse = new HashMap<>();
        for (int num : nums) {
            int diff = num - reverse(num);
            selfMinusReverse.put(diff, selfMinusReverse.getOrDefault(diff, 0) + 1);
        }
        long ans = 0L;
        for (Map.Entry<Integer, Integer> entry : selfMinusReverse.entrySet()) {
            ans += (long) entry.getValue() * (entry.getValue() - 1) / 2;
        }
        return (int) (ans % 1000000007L);
    }

    private int reverse(int num) {
        int res = 0;
        while (num > 0) {
            res = res * 10 + num % 10;
            num /= 10;
        }
        return res;
    }
}

学习笔记：
这其实也算是一道写着中等题的困难题了。
看到1 <= nums.length <= 10^5就知道n^2的时间复杂度会过不去了。
那么就不能使用暴力解法。

巧妙的地方就是在于
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
这个公式让你会觉得需要i和j两个都一起算才能知道是否相等。
移项整理后会发现
其实上只需要自己算一下差就可以了。
nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])
所以就要统计一下，每个数字减自身反转后的差有多少相同，然后统计即可。

然后要注意最后是value * (value - 1) / 2这样的形式。
为什么是这样呢，因为题目规定i < j。
也就是说i不能和j一样，所以要-1。然后i和j不能调换再算一次，所以要/2。