使用XOR方法查找数组重复元素的C++代码问题排查

给定一个长度为n的整数数组nums，其中所有整数都在[1, n]范围内，每个整数出现一次或两次，请返回所有出现两次的整数组成的数组。要求算法时间复杂度为O(n)，且仅使用常数额外空间。

我的代码 #

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {   
        
        vector<int> final;
        int ans=0;
        
        // XOR n ke liye
        for(int i=0;i<nums.size();i++)
        {
            ans=ans^nums[i];
        }
        final.push_back(ans);
    
        // XOR n-1 ke liye
        for(int i=1;i<nums.size();i++)
        {
            ans=ans^i;
        }
        final.push_back(ans);
        return final;
    }
};

测试情况 #

• 输入：[4,3,2,7,8,2,3,1]
• 预期输出：[2,3]
• 实际输出：[10,10]

问题分析 #

你的代码逻辑完全错误：

• XOR的思路仅适用于数组中只有一个重复元素的场景，而题目要求找出所有出现两次的元素，这种方法从根上就不适用。
• 你把两次XOR的结果直接塞进数组返回，完全不符合题目要求的输出格式。

正确解法 #

核心思路 #

利用数组元素范围在[1, n]的特性，把数组本身当作哈希表：每个数num对应索引num-1，通过标记该索引位置元素的正负来判断是否重复。如果对应索引的元素已经是负数，说明这个数之前出现过，就是重复项。

代码实现 #

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        for (int num : nums) {
            int idx = abs(num) - 1;
            if (nums[idx] < 0) {
                res.push_back(abs(num));
            } else {
                nums[idx] = -nums[idx];
            }
        }
        return res;
    }
};

步骤解释 #

1. 遍历数组中的每个元素num，计算对应的索引idx = abs(num) - 1（取绝对值是因为之前可能已经把元素取反过）。
2. 检查nums[idx]：如果是负数，说明之前已经遇到过abs(num)，把它加入结果数组；如果是正数，就将其取反，标记为已访问。
3. 遍历完成后，结果数组就是所有出现两次的元素。

内容的提问来源于stack exchange，提问作者Sam's Show