LeetCode442 数组中重复的数据｜原地哈希空间优化算法C++深度题解

大家好，今日完成中等难度数组算法刷题，攻克面试高频空间限制难题。
本题核心考点：严格限制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;
}
};

算法考点总结

原地数组哈希是数组面试王牌解法，专门解决数值范围和数组长度匹配的查找、重复问题。
不用额外哈希容器，原地修改正负标记出现次数，是字节、华为、腾讯高频笔试原题，吃透数组下标映射思维，区间查找题型全部通用。