统计一个数组中好对子的个数-LeetCode

1814. 统计一个数组中好对子的个数

🎯 问题描述

描述：
给你一个非负整数数组 nums。
如果满足 0 <= i < j < nums.length 且：

$$nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])$$

那么我们称 (i, j) 是一个好对子。
其中 rev(x) 表示将整数 x 的各位数字反转（例如 rev(123) = 321，rev(120) = 21）。
请你返回好对子的数目。由于答案可能很大，请返回它对 $10^9 + 7$ 取余的结果。

说明：

• 这是一个哈希表计数结合数学恒等变形的问题。

• 核心难点：直接暴力枚举所有 (i, j) 对需要 $O(N^2)$ 时间，效率太低。

• 策略：通过移项变形，将涉及 i 和 j 的项分离，找到每个元素独立的特征值（差值），将问题转化为“寻找具有相同特征值的元素对”。

• 示例：

• 示例 1：

输入：nums = [42,11,1,97]
输出：2
解释：
- 变换公式：nums[x] - rev(nums[x])
- i=0, val=42, diff = 42 - 24 = 18
- i=1, val=11, diff = 11 - 11 = 0
- i=2, val=1,  diff = 1 - 1 = 0
- i=3, val=97, diff = 97 - 79 = 18
- 差分为 18 的有：(0, 3) -> 1对
- 差分为 0 的有：(1, 2) -> 1对
- 总共 2 对。

💻 解题思路

思路1：数学变换 + 哈希表计数

核心逻辑

1. 公式变形：
   原条件：$nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])$
   移项得：$nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])$
2. 特征提取：
   定义一个元素的特征值为 $diff = val - rev(val)$。
   如果两个元素的下标 $i < j$ 且它们的特征值 $diff$ 相等，那么它们就构成一个好对子。
3. 计数策略：
   遍历数组，对于每个元素计算其 $diff$。
   • 如果这个 $diff$ 之前出现过 $k$ 次，说明当前元素可以和之前的 $k$ 个元素分别组成好对子，答案增加 $k$。
   • 然后将当前 $diff$ 的计数加 1。

代码实现

class Solution:
    def countNicePairs(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        ans = 0
        # 哈希表：键为差分值 (num - rev(num))，值为该差分出现的次数
        count = defaultdict(int)
        
        for j, num in enumerate(nums):
            # 1. 计算当前数字的反转值
            rev_j = int(str(num)[::-1])
            
            # 2. 计算特征差分
            # 根据公式变形：nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])
            diff = num - rev_j
            
            # 3. 累加计数
            # 如果之前出现过相同的 diff，说明可以组成好对子
            if diff in count:
                ans += count[diff]
            
            # 4. 更新计数
            count[diff] += 1
            
        return ans % mod 

📊 性能分析

• 时间复杂度：$O(N \times \log M)$
  • 其中 $N$ 是数组长度，$M$ 是数组中的最大值。
  • 遍历数组需要 $O(N)$。
  • 每次计算反转 int(str(num)[::-1]) 需要 $O(\log_{10} M)$ 的时间（数字的位数）。
  • 哈希表操作平均为 $O(1)$。
• 空间复杂度：$O(N)$
  • 哈希表 count 在最坏情况下存储 $N$ 个不同的差分值。

思考

1. 数学变换的重要性：

   • 这是解题的关键。如果不进行移项，我们无法将 $i$ 和 $j$ 的贡献分离开来独立计算。
   • 变换后，问题变成了“寻找具有相同属性（差分）的元素对”，这是哈希表的经典应用场景。

2. 累加计数的原理：

   • 代码使用了 ans += count[diff]。
   • 假设某个差分值 $D$ 之前出现了 $k$ 次（下标为 $p_1, p_2, ..., p_k$）。
   • 当前遇到了下标 $j$，且 $diff_j = D$。
   • 因为 $p_1 < p_2 < ... < p_k < j$，所以 $(p_1, j), (p_2, j), ..., (p_k, j)$ 都是合法的好对子。
   • 一共增加了 $k$ 对。

3. 反转操作的实现：

   • int(str(num)[::-1]) 是 Python 中反转整数的常用技巧。
   • 它先将数字转为字符串，利用切片 [::-1] 反转字符串，再转回整数。
   • 这种方法简单且不易出错（自动处理前导零，如 120 反转为 21）。

4. 取模运算：

   • 题目要求对 $10^9 + 7$ 取模。
   • 由于答案可能很大（最坏情况是 $N(N-1)/2$），需要在返回时取模。
   • 也可以在每次 ans += ... 时取模，防止溢出（虽然在 Python 中整数不会溢出，但在其他语言中需要注意）。

5. 边界情况：

   • 数组长度为 1：无法组成数对，返回 0。
   • 所有数字都相同：例如 [5, 5, 5]。5 - 5 = 0。所有差分都为 0。对数为 $C_3^2 = 3$。
   • 没有好对子：所有差分都不同，返回 0。