今天是母亲节，祝全天下的母亲节日快乐。
本文首发于馆主君晓的博客，05-08
题目内容
??442. 数组中重复的数据，题目截图如下：
题目分析
??这个题目第一眼一般就能够想到使用哈希表来做，还是老步骤。我们先来转述下题目的意思，题目是说，给你一个长度为n的整数数组，并且数组里的所有整数都在范围[1,n]之间，并且每个整数要么出现一次，要么出现两次，然后你需要找出出现两次的数字，并且将其返回。
??思路一，使用c++的unordered_map，我们只需要使用一次循环，循环遍历数组，将数组的元素作为key放在map里，如果key已经存在了那么久将其放入结果数组中，循环结束，我们的元素也就找出来了。
class Solution {
private:
unordered_map<int,int> map;
public:
vector<int> findDuplicates(vector<int>& nums) {
int n = nums.size();
vector<int> res;
for(int i = 0;i<n;i++){
if(map.find(nums[i])!=map.end()){
map[nums[i]]+=1;
res.push_back(nums[i]);
}else{
map[nums[i]] = 1;
}
}
return res;
}
};
??但是上面的思路耗时太久，我们可以尝试第二种思路，首先排序然后使用双指针，按照升序的方式进行排序，之后一前一后指针，如果两个指针所指的元素相等，那么就将元素放入结果数组。
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
// 排序+双指针
vector<int> res;
int n = nums.size();
if(n==1){
return res;
}
sort(nums.begin(),nums.end());
int back = 0,front = 1;
while(front<n){
if(nums[back]==nums[front]){
res.push_back(nums[back]);
}
back++;
front++;
}
return res;
}
};
??上面的思路的确可以，但是其实不符合题目要求，题目要求时间复杂度为o(n)，空间复杂度为常数。于是就有了下面的第三种方式，原地哈希。直接看代码可能比较好懂：
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
// 原地数组
vector<int> res;
int n = nums.size();
if(n==1){
// 特殊处理
return res;
}
for(int i = 0;i<n;i++){
// 获取nums[i]的绝对值 因为可能为负数 负数是因为我们取反了
int x = abs(nums[i]);
if(nums[x-1]>0){
// 下标所处位置的元素大于0 说明还没被取负 取负的都是我们第一次碰见的数
nums[x-1] =-nums[x-1];
}else{
// 已经取负了 所以现在这次相当于第二次碰见这个数 那么就加入结果数组
res.push_back(x);
}
}
return res;
}
};
代码实现
??代码实现如上所示。
结语
??父母在，不远游，游必有方。
