What does 'almost equal' mean in Count Almost Equal Pairs II?

Two numbers are almost equal if they can become identical after applying the operation at most twice.

How should I handle duplicates when counting pairs?

Use a hash table to track counts of each transformed number and increment totals carefully to avoid double counting.

What is the best approach for large arrays up to 5000 elements?

Scan the array while generating transformations for each element and use hash lookup to efficiently count matches.

Can this problem be solved without a hash table?

Yes, but it will likely be less efficient and more prone to missing or double-counting almost equal pairs.

Why is array scanning plus hash lookup the primary pattern?

Because we need to enumerate transformations per element and quickly find how many previous numbers match, which this pattern handles efficiently.

#3267

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计近似相等数对 II

注意：在这个问题中，操作次数增加为至多两次。给你一个正整数数组 nums 。如果我们执行以下操作至多两次可以让两个整数 x 和 y 相等，那么我们称这个数对是近似相等的：选择 x 或者 y 之一，将这个数字中的两个数位交换。请你返回 nums 中，下标 i 和 j 满足 i …

数组哈希表排序计数枚举

题目描述

注意：在这个问题中，操作次数增加为至多两次。

给你一个正整数数组 nums 。

如果我们执行以下操作 至多两次 可以让两个整数 x 和 y 相等，那么我们称这个数对是 近似相等 的：

选择 x 或者 y 之一，将这个数字中的两个数位交换。

请你返回 nums 中，下标 i 和 j 满足 i < j 且 nums[i] 和 nums[j] 近似相等 的数对数目。

注意，执行操作后得到的整数可以有前导 0 。

示例 1：

输入：nums = [1023,2310,2130,213]

输出：4

解释：

近似相等数对包括：

1023 和 2310 。交换 1023 中数位 1 和 2 ，然后交换数位 0 和 3 ，得到 2310 。
1023 和 213 。交换 1023 中数位 1 和 0 ，然后交换数位 1 和 2 ，得到 0213 ，也就是 213 。
2310 和 213 。交换 2310 中数位 2 和 0 ，然后交换数位 3 和 2 ，得到 0213 ，也就是 213 。
2310 和 2130 。交换 2310 中数位 3 和 1 ，得到 2130 。

示例 2：

输入：nums = [1,10,100]

输出：3

解释：

近似相等数对包括：

1 和 10 。交换 10 中数位 1 和 0 ，得到 01 ，也就是 1 。
1 和 100 。交换 100 中数位 1 和从左往右的第二个 0 ，得到 001 ，也就是 1 。
10 和 100 。交换 100 中数位 1 和从左往右的第一个 0 ，得到 010 ，也就是 10 。

提示：

2 <= nums.length <= 5000
1 <= nums[i] < 10⁷

lightbulb

解题思路

方法一：排序 + 枚举

我们可以枚举每一个数，然后对于每一个数，我们可以枚举每一对不同的数位，然后交换这两个数位，得到一个新的数，记录到一个哈希表 $\textit{vis}$ 中，表示这个数至多进行一次交换后的所有可能的数，然后继续枚举每一对不同的数位，交换这两个数位，得到一个新的数，记录到哈希表 $\textit{vis}$ 中，表示这个数至多进行两次交换后的所有可能的数。

这样枚举，会少统计一些数对，比如 $[100, 1]$ ，因为 $100$ 交换后的数是 $1$ ，而此前枚举过数不包含 $1$ ，因此会少统计一些数对。我们只需要在枚举之前，将数组排序，即可解决这个问题。

时间复杂度 $O(n \times (\log n + \log^5 M))$ ，空间复杂度 $O(n + \log^4 M)$ 。其中 $n$ 是数组 $\textit{nums}$ 的长度，而 $M$ 是数组 $\textit{nums}$ 中的最大值。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def countPairs(self, nums: List[int]) -> int:
        nums.sort()
        ans = 0
        cnt = defaultdict(int)
        for x in nums:
            vis = {x}
            s = list(str(x))
            m = len(s)
            for j in range(m):
                for i in range(j):
                    s[i], s[j] = s[j], s[i]
                    vis.add(int("".join(s)))
                    for q in range(i + 1, m):
                        for p in range(i + 1, q):
                            s[p], s[q] = s[q], s[p]
                            vis.add(int("".join(s)))
                            s[p], s[q] = s[q], s[p]
                    s[i], s[j] = s[j], s[i]
            ans += sum(cnt[x] for x in vis)
            cnt[x] += 1
        return ans

speed

复杂度分析

指标	值
时间	complexity depends on the number of transformations generated per element and the efficiency of hash lookups, while space complexity is dominated by storing all reachable numbers in a hash table.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Notice the problem emphasizes array scanning combined with hash lookup.
question_mark
Be aware that generating all possible transformations per element may affect performance.
question_mark
Watch for edge cases where multiple transformations lead to the same integer.

warning

常见陷阱

外企场景

error
Failing to account for exactly two operations per element may lead to incorrect counts.
error
Double counting pairs if the hash table is updated before scanning all potential matches.
error
Ignoring large values in nums, which can cause hash table collisions or overflow if not handled carefully.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count almost equal pairs with only one allowed operation instead of two.
arrow_right_alt
Find almost equal pairs in a multidimensional array using similar transformation rules.
arrow_right_alt
Limit the operations to additive changes and count pairs satisfying the restricted criteria.

help

常见问题

外企场景

继续练习

#3265 统计近似相等数对 I #3186 施咒的最大总伤害 #3371 识别数组中的最大异常值