1~n数组重复与缺失数字求解的Python代码错误排查

给定一个包含n个整数的只读数组，数组元素取值范围为1到n。
数组中除整数A出现两次、整数B缺失外，其余每个整数均恰好出现一次。
请返回A和B。

• 算法需满足线性时间复杂度，优先实现不使用额外内存的解法
• 返回结果中A（重复数）需要排在B（缺失数）之前

示例 #

输入：[3, 1, 2, 5, 3]
输出：[3, 4]
说明：重复数A=3，缺失数B=4

• 遍历逻辑错误：for i in A 中i是数组元素值，不是下标，代码中asum+=A[i]、A[i] in dict的写法属于取值错误，当元素值等于数组长度时还会触发下标越界
• 哈希判断逻辑错误：写入字典时用dict[i]=1（键为元素值），判断存在性时却查A[i]，键不匹配导致重复值识别失效
• 空间复杂度不达标：使用字典存储遍历记录的方案额外空间为O(n)，未实现常数额外空间的优化要求

方案1：数学求和法（易理解，线性时间） #

通过1~n的理论总和和数组实际总和的差值关系，结合找到的重复数直接算出缺失数，逻辑简单易实现：

class Solution:
    def repeatedNumber(self, A):
        n = len(A)
        expected_sum = n * (n + 1) // 2  # 1到n的理论总和
        actual_sum = 0
        seen = set()
        repeat = 0
        for num in A:
            actual_sum += num
            if num in seen:
                repeat = num
            seen.add(num)
        # 推导公式：理论总和 = 实际总和 - 重复数 + 缺失数
        missing = expected_sum - actual_sum + repeat
        return [repeat, missing]

方案2：异或法（最优解，常数额外空间） #

利用异或运算「相同数异或为0、不同数异或保留差异位」的特性，不需要额外哈希空间，完全适配只读数组、常数空间的要求：

class Solution:
    def repeatedNumber(self, A):
        n = len(A)
        xor_res = 0
        # 所有数组元素 + 1~n所有数一起异或，最终结果为 重复数 ^ 缺失数
        for num in A:
            xor_res ^= num
        for i in range(1, n + 1):
            xor_res ^= i
        # 取最右侧为1的二进制位作为分组掩码
        mask = xor_res & -xor_res
        group1, group2 = 0, 0
        # 按掩码位把所有数分成两组，分别异或得到两个候选数
        for num in A:
            if num & mask:
                group1 ^= num
            else:
                group2 ^= num
        for i in range(1, n + 1):
            if i & mask:
                group1 ^= i
            else:
                group2 ^= i
        # 遍历数组判断哪个是重复数
        for num in A:
            if num == group1:
                return [group1, group2]
        return [group2, group1]

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