What is the main trick to solve Count Nice Pairs in an Array efficiently?

The key is transforming the condition into nums[i] - rev(nums[i]) == nums[j] - rev(nums[j]) and using a hash map to count frequencies.

Why do we use modulo 10^9+7 in this problem?

The number of nice pairs can be very large, and modulo prevents integer overflow while satisfying problem constraints.

Can we use a nested loop for Count Nice Pairs?

Yes, but nested loops lead to O(n^2) time complexity, which is too slow for arrays of size up to 10^5.

How do you reverse numbers correctly in this context?

Convert the number to a string, reverse the string, then convert back to integer, handling leading zeros appropriately.

Does GhostInterview help with verifying large input arrays?

Yes, it simulates hash-based counting and ensures the modulo arithmetic is applied correctly for large arrays.

#1814

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计一个数组中好对子的数目

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

数组哈希表数学计数

题目描述

给你一个数组 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⁹ + 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 <= 10⁵
0 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：式子变换 + 哈希表

对于下标对 $(i, j)$ ，如果满足条件，那么有 $nums[i] + rev(nums[j]) = nums[j] + rev(nums[i])$ ，即 $nums[i] - nums[j] = rev(nums[j]) - rev(nums[i])$ 。

因此，我们可以将 $nums[i] - rev(nums[i])$ 作为哈希表的键，统计每个键出现的次数。最后计算每个键对应的值的组合数，相加得到最终的答案。

注意答案的取模操作。

时间复杂度 $O(n \times \log M)$ ，其中 $n$ 和 $M$ 分别是数组 nums 的长度和数组 nums 中的最大值。空间复杂度 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        def rev(x):
            y = 0
            while x:
                y = y * 10 + x % 10
                x //= 10
            return y

        cnt = Counter(x - rev(x) for x in nums)
        mod = 10**9 + 7
        return sum(v * (v - 1) // 2 for v in cnt.values()) % mod

speed

复杂度分析

指标	值
时间	complexity is O(n) because each element is processed once. Space complexity is O(n) for the hash map storing difference counts.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Look for an O(n^2) brute force first but quickly pivot to hash-based counting.
question_mark
Expect candidates to notice the subtraction transformation nums[i] - rev(nums[i]).
question_mark
Emphasize handling modulo arithmetic correctly to prevent overflow.

warning

常见陷阱

外企场景

error
Attempting nested loops leads to O(n^2) and timeouts on large arrays.
error
Forgetting to reverse numbers correctly can produce incorrect counts.
error
Neglecting modulo 10^9+7 results in integer overflow for large arrays.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count pairs where nums[i] + rev(nums[j]) - nums[j] - rev(nums[i]) equals a target value instead of zero.
arrow_right_alt
Find nice pairs in a subarray or with additional constraints on index distance.
arrow_right_alt
Return the actual index pairs rather than just the count, preserving order.

help

常见问题

外企场景

继续练习

#1994 好子集的数目 #2001 可互换矩形的组数 #1512 好数对的数目