【ACWing】13. 找出数组中重复的数字

https://www.acwing.com/problem/content/description/14/

给定一个长度为 n n n的整数数组 A A A，数组中所有的数字都在 0 ∼ n − 1 0∼n−1 0∼n−1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
注意：如果某些数字不在 0 ∼ n − 1 0∼n−1 0∼n−1的范围内，或数组中不包含重复数字，则返回 − 1 -1 −1；

首先判断每个数是否在范围里，如果不在则直接返回 − 1 -1 −1。把每个数都加上 1 1 1，然后对于 A [ i ] A[i] A[i]，将 A [ A [ i ] − 1 ] A[A[i]-1] A[A[i]−1]这个数变成负的，以此来标记哪些数出现过。如果遍历到某个 A [ j ] A[j] A[j]的时候发现 A [ ∣ A [ j ] ∣ − 1 ] A[|A[j]|-1] A[∣A[j]∣−1]这个数已经为负，那说明 ∣ A [ j ] ∣ |A[j]| ∣A[j]∣这个数重复出现过，返回之。代码如下：

#include 
using namespace std;

class Solution {
public:
    int duplicateInArray(vector& nums) {
        for (auto &x : nums) {
            if (x < 0 || x >= nums.size()) return -1;
            x++;
        }

        for (int i = 0; i < nums.size(); i++) {
            int x = nums[i], y = abs(x) - 1;
            if (nums[y] < 0) return abs(x) - 1;
            nums[y] = -nums[y];
        }

        return -1;
    }
};

时间复杂度 O ( n ) O(n) O(n)，空间 O ( 1 ) O(1) O(1)。