3761.镜像对之间最小绝对距离

🎯 问题描述

描述：
给你一个整数数组 nums。
如果两个下标 i 和 j 满足 nums[i] 和 nums[j] 互为镜像数（即一个数是另一个数的数字反转，例如 123 和 321），则称它们构成一个镜像对。
请你返回所有镜像对中，下标距离 |i - j| 的最小值。
如果不存在镜像对，返回 -1。

说明：

这是一个哈希表结合贪心策略的问题。
镜像定义：x 的镜像是 reverse(x)。注意，如果一个数是回文数（如 121），它的镜像是它自己。
核心难点：我们需要同时匹配 x 和 reverse(x)。
策略：利用哈希表存储“最近一次出现的位置”。关键在于，我们将原数和镜像数映射到同一个逻辑空间中进行更新。
示例：
示例 1：

输入：nums = [12, 21, 3, 3]
输出：2
解释：
- i=0, num=12. 镜像=21. 哈希表更新 count[12]=0, count[21]=0.
- i=1, num=21. 检查 count[21]. 存在(值为0). 距离 = |1-0|=1. 更新 count[21]=1.
- i=2, num=3. 镜像=3. 检查 count[3]. 不存在. 更新 count[3]=2.
- i=3, num=3. 检查 count[3]. 存在(值为2). 距离 = |3-2|=1.
- 最小距离是 1.

💻 解题思路

思路1：动态哈希更新（同槽竞争法）

核心逻辑

我们需要找到 nums[i] 和之前出现的某个数 nums[j]，使得 nums[i] == reverse(nums[j])。
这等价于 reverse(nums[i]) == nums[j]。

代码采用了一种非常紧凑的写法：

查找：检查当前数字 num 是否已经在哈希表中。
- 如果 num 在表中，说明之前出现过 num 或者出现过 num 的镜像（因为之前的某个数的镜像计算结果可能正好是 num，并存入了表中）。
- 计算距离并更新答案。
更新：计算当前数字的镜像 m。
- 将 m 的位置更新为当前下标 i：count[m] = i。
- 精妙之处：
  - 如果当前是 12，我们存入 count[21] = i。这意味着：“如果你在后面遇到了 21，请记得我（12）在这里”。
  - 如果当前是 21，我们存入 count[12] = i。这意味着：“如果你在后面遇到了 12，请记得我（21）在这里”。
  - 如果当前是 121（回文），我们存入 count[121] = i。

代码实现

class Solution:
    def minMirrorPairDistance(self, nums: List[int]) -> int:
        ans = float('inf')
        # 键：数字（原数或镜像数），值：该数字最近一次“有效”出现的下标
        count = defaultdict(int)
        
        for i, num in enumerate(nums):
            # 1. 查找：当前数字 num 是否能和之前的某个数配对？
            # 如果 num 在 count 中，说明之前有一个数，它的镜像是 num（或者它本身就是 num 且是回文）
            if num in count:
                d = abs(i - count[num])
                ans = min(d, ans)
            
            # 2. 更新：计算当前数字的镜像
            # 将 num 转为字符串，反转，再转回整数
            m = int(str(num)[::-1])
            
            # 3. 存入哈希表
            # 我们存储的是“镜像数”的位置
            # 逻辑含义：对于未来的数字 x，如果 x 等于 m，那么 x 就可以和当前的 i 配对
            count[m] = i
            
        return ans if ans <= 10**9 else -1

📊 性能分析

时间复杂度： $O(N \times \log M)$ $O (N \times lo g M)$
- 其中 $N$ 是数组长度， $M$ 是数字的最大值。
- 遍历数组 $O(N)$ 。
- 字符串反转操作 str(num)[::-1] 耗时 $O(\log_{10} M)$ 。
- 哈希表操作平均 $O(1)$ 。
空间复杂度： $O(N)$ $O (N)$
- 哈希表存储数字及其下标。

💡 思考

“同槽竞争”机制：
- 这是代码最精彩的地方。
- 通常我们会想：count[num] = i。
- 但这里我们存的是 count[mirror(num)] = i。
- 这意味着哈希表的键不仅是“数字本身”，而是“谁能和我配对”。
- 例如：遇到 12，我们在 count[21] 处写下 i。如果后面真的来了 21，它查 count[21] 就能找到 12 的位置。
回文数的处理：
- 如果 num = 121，则 m = 121。
- 代码执行 count[121] = i。
- 如果后面又来了 121，它查 count[121] 能找到前一个 121。
- 逻辑完美自洽。
为什么不需要存 count[num]？
- 若两数分别为 120 和21
- 21的反转12不在哈希表里
边界情况：
- 数组长度 1：无法配对，返回 -1。
- 没有镜像对：ans 保持 inf，返回 -1。
- 大数：int(str(num)[::-1]) 能正确处理。
代码细节：
- ans <= 10**9：这是一个哨兵判断。因为题目中距离最大也就是 $N$ ，如果 ans 还是初始的大值（或者题目给定的无穷大），说明没找到。