Leetcode 442.数组中重复的数据

原题链接：Leetcode 442. Find All Duplicates in an Array

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears once or twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant extra space.

Example 1:

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

Example 2:

Input: nums = [1,1,2]
Output: [1]

Example 3:

Input: nums = [1]
Output: []

Constraints:

• n == nums.length
• 1 <= n <= 10⁵
• 1 <= nums[i] <= n
• Each element in nums appears once or twice.

本来我一看这题，觉得这不是easy？排序一下遍历一遍就好了，也过了
后来发现他规定了时间复杂度O(n)，空间复杂度O(1)，那么sort()就不能用了

因此，就有一个思路，对于 nums[i] ，将下标为nums[i] - 1的位置的数字进行映射（还要能映射回去）。
映射方法通常有两种：

• 取反
• 增加偏移量

取反的思路就是，从起始位置进行遍历，每次将下标为 nums[i]−1 的数字取反；
当遍历到值nums[i] 为负数，需要忽略其负号。
若发现下标为nums[i]−1 的数字已经是负数，说明之前出现过同样的数字nums[i]，即找到了重复数字。

class Solution {
public:
    vector findDuplicates(vector& nums) {
        vector ans;

        for(int i = 0; i < nums.size(); i++ ){
            if(nums[abs(nums[i]) - 1] < 0) ans.push_back(abs(nums[i]));
            nums[abs(nums[i]) - 1] *= -1;
        }
        return ans;
    }
};

• 时间复杂度：O(n)，遍历一遍
• 空间复杂度：O(1)，输出不算复杂度