技巧题目,数组本省作为hash表
C++ 代码
class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
// 正常考虑使用hash表,这里使用数组自身作为hash表,使用负号表示之前出现过一次
// 注意下标 -1 的映射
for(int i=0; i<nums.size(); ++i) {
int num = abs(nums[i])-1;
// printf("%d,%d\n", num, nums[num]);
if(nums[num] < 0)res.push_back(num+1);
else nums[num] *= -1;
}
return res;
}
};