leetcode 442. Find All Duplicates in an Array

1.题目

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.
Find all the elements that appear twice in this array.
给一个数组，数组元素在范围[1,n]，n是数组长度。其中，有些数字出现两次，有些数字只出现一次。
找出出现两次的元素，不开辟额外空间，时间复杂度O(n)
Could you do it without extra space and in O(n) runtime?

Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

2.分析

找出出现两次的元素，复杂度O(n)，数组遍历一遍。
由于元素大小在范围[1,n]，数组下标范围[0,n-1]刚好对应。
对于已经出现的元素x，A[x-1] 为 -A[x-1]。下次再标记时发现已经为负数则表示该数字已经出现过。

3.代码

class Solution {
public:
    vector<int> findDuplicates(vector<int>& nums) {
        vector<int> ans;
        for (int x : nums) {
            x = abs(x);
            if (nums[x - 1] < 0)
                ans.push_back(x);
            else
                nums[x - 1] *= -1;
        }
        return ans;
    }
};