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

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