数组中交换两位数字可匹配的唯一配对数求解，要求时间复杂度低于O(n²)

求解数组中的唯一配对数量，配对要求为：其中一个数字交换任意两位数字一次后即可得到另一个数字。

输入数组：

arr = [3,23,156,4324,324,651,165,32]

符合要求的唯一配对共3个：(32,23)、(156,165)、(651,156)，输出为3。
注意：165和651不属于符合要求的配对，因为本题仅允许交换一次两位数字，二者转换需要两次交换。
要求解法的时间复杂度低于O(n²)。

你目前的实现直接使用itertools.combinations遍历所有两两组合，本身时间复杂度就是O(n²)，当数组元素较多时必然超时，且判断交换一次的逻辑也存在问题，只能筛选出完全相等的数字。

可以采用哈希表统计的思路，整体时间复杂度控制在O(n * k²)，其中k为数字的最大位数，远低于O(n²)：

1. 预处理：将数组中的数字按字符串长度分组，长度不同的数字不可能通过一次交换互相转换，无需参与后续判断
2. 对每个长度分组单独处理：
   • 初始化一个哈希表seen，用于记录已经遍历过的数字的字符串形式的出现次数
   • 遍历分组内的每个数字，先将其转为字符串s
   • 生成s交换任意两位一次后的所有可能字符串（去重），统计seen中这些字符串的出现次数总和，加到最终配对数里
   • 最后将s加入seen，计数加1

def count_swap_pairs(arr):
    from collections import defaultdict
    # 按数字的字符串长度分组
    len_groups = defaultdict(list)
    for num in arr:
        s = str(num)
        len_groups[len(s)].append(s)
    
    total = 0
    for group in len_groups.values():
        seen = defaultdict(int)
        for s in group:
            n = len(s)
            # 生成所有交换一次后的可能字符串
            swap_candidates = set()
            for i in range(n):
                for j in range(i+1, n):
                    # 交换i和j位
                    s_list = list(s)
                    s_list[i], s_list[j] = s_list[j], s_list[i]
                    swap_candidates.add(''.join(s_list))
            # 统计之前出现过的符合要求的数量
            for candidate in swap_candidates:
                total += seen.get(candidate, 0)
            # 把当前字符串加入已见集合
            seen[s] += 1
    return total

# 测试示例
arr = [3,23,156,4324,324,651,165,32]
print(count_swap_pairs(arr)) # 输出3

如果需要单独判断两个等长数字是否符合要求，可直接逐位对比：

1. 收集两个字符串对应位置字符不同的索引
2. 若不同的索引数量不等于2，直接返回False
3. 若两个索引位置的字符交叉相等（即s1[i] == s2[j]且s1[j] == s2[i]），返回True，否则返回False

内容的提问来源于stack exchange，提问作者bloomsdayforever