大家好，今日完成中等难度数组算法刷题，攻克面试高频空间限制难题。
本题核心考点：严格限制O(n)时间复杂度、只能常数额外空间，不能新开哈希表，力扣经典数组思维题。
 
题目题意
 
长度为n的数组，数字范围全部在 [1,n] 之间，每个数字最多出现2次，找出所有出现2次的数字。
硬性要求：不能使用map、set等额外哈希容器，只能原地修改数组完成求解。
 
核心原地哈希算法思路
 
利用题目数字特性：数组长度n、数值范围1~n，数字 x 天然可以对应数组下标 x-1 ，用原数组自身做哈希表，完全不占用额外空间。
 
1. 遍历每一个数字，取出绝对值得到当前数值 x 
2. 找到对应映射下标  index = x-1 
3. 判断下标位置数字正负：- 数字为负数：代表这个下标对应的数字之前已经出现过，当前数字就是重复答案
- 数字为正数：把下标位置数字取反变负数，做出现标记
4. 全程只遍历一遍数组，时间O(n)，空间只有答案数组，完全符合题目常数空间要求
 
样例原理讲解
 
输入  [4,3,2,7,8,2,3,1] 
数字4 → 下标3，把nums[3]取反
数字3 → 下标2，把nums[2]取反
遍历到数字2时，对应下标1位置已经是负数，证明2重复，加入答案
遍历到数字3时，对应下标2位置已经是负数，证明3重复，加入答案
最终输出 [2,3] ，和样例完全匹配
 
C++完整AC可运行代码
 
class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> res;
        // 原地数组哈希：数值nums[i]对应下标nums[i]-1
        for(int i=0;i<nums.size();i++){
            int idx = abs(nums[i]) - 1;
            // 位置已经被标记过，说明当前数字重复
            if(nums[idx] < 0){
                res.push_back(abs(nums[i]));
            }
            // 取反标记，代表数字已经出现过一次
            nums[idx] = -nums[idx];
        }
        return res;
    }
};
 
算法考点总结
 
原地数组哈希是数组面试王牌解法，专门解决数值范围和数组长度匹配的查找、重复问题。
不用额外哈希容器，原地修改正负标记出现次数，是字节、华为、腾讯高频笔试原题，吃透数组下标映射思维，区间查找题型全部通用。