题目描述

给你一个数组 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])

请你返回好下标对的数目。由于结果可能会很大，请将结果对 10^9 + 7 取余 后返回。

样例

输入：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 。

输入：nums = [13,10,35,24,76]
输出：4

限制

• 1 <= nums.length <= 10^5
• 0 <= nums[i] <= 10^9

算法

(哈希表) $O(n \log S)$

1. 将条件进行等价转换，即 nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])。
2. 通过哈希表计算出每个数字对应的 x - rev(x) 的值。
3. 枚举哈希表，每个 key 贡献的答案为 value * (value - 1) / 2。

时间复杂度

• 构建哈希表的时间复杂度为 $O(n \log S)$。其中 $S$ 为最大的数字。
• 求答案仅需要 $O(n)$ 的时间，故总时间复杂度为 $O(n \log S)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储哈希表。

C++ 代码

#define LL long long

class Solution {
private:
    int rev(int x) {
        queue<int> q;
        int res = 0;
        while (x) {
            q.push(x % 10);
            x /= 10;
        }

        while (!q.empty()) {
            res = res * 10 + q.front();
            q.pop();
        }

        return res;
    }

public:
    int countNicePairs(vector<int>& nums) {
        unordered_map<int, int> seen;
        for (int x : nums)
            seen[x - rev(x)]++;

        const int mod = 1000000007;
        int ans = 0;
        for (const auto &[_, v] : seen)
            ans = (ans + (LL)(v) * (v - 1) / 2) % mod;

        return ans;
    }
};