题目的主要信息：

• 数组中n+1个元素，包括1到n的所有整数
• 找到重复的那个数字
• 额外要求：时间复杂度$O(n)O(n)$，空间复杂度$O(1)O(1)$

方法一：排序法（能通过，时间不符合要求）

具体做法： 利用sort函数对数组排序，遍历数组，相邻两个数相同则找到所求。

class Solution {
public:
    int search(int n, vector<int>& a) {
        sort(a.begin(), a.end()); //排序
        for(int i = 1; i <= n; i++){ //找相邻重复
            if(a[i] == a[i - 1])
                return a[i];
        }
        return 0;
    }
};

复杂度分析：

• 时间复杂度：$O(nlo{g}_{2}n)O(nlog\_2n)$，sort函数排序的时间复杂度
• 空间复杂度：$O(1)O(1)$，无额外空间使用

方法二：无序哈希表（能通过，空间不符合要求）

具体做法： 利用无序哈希表unordered_map记录所有数字，遍历数组每遇到一个数查看是否已经在哈希表中，如果在，则返回该数，如果不在则加入哈希表中。

class Solution {
public:
    int search(int n, vector<int>& a) {
        unordered_map<int, int> mp;
        for(int i = 0; i <= n; i++){
            if(mp.find(a[i]) != mp.end()) //利用哈希表O(1)时间内查找
                return a[i];
            else
                mp[a[i]] = 1;
        }
        return 0;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，unordered_map访问是在$O(1)O(1)$，一共最多遍历$n+1n+1$次
• 空间复杂度：$O(n)O(n)$，建立的哈希表最坏长度为$nn$

方法三：异或运算

具体做法： 异或运算两个法则：$a⨁a=0a\backslash bigoplus\; a=0$、$a⨁0=aa\backslash bigoplus0=a$，因此我们只要对这$n+1n+1$个数字逐一进行累异或运算，相同的两个数会被抵消掉，而我们再与1到n逐一做累异或运算，1到n中非重复的那个数字会被前面没有重复的数字抵消掉，最后只剩下重复的数字。

class Solution {
public:
    int search(int n, vector<int>& a) {
        int res = 0; //0异或所有数字等那个数字本身
        for(int i = 0; i <= n; i++){
            if(i != 0){  //非0异或数组元素及1到n数字本身
                res ^= a[i];
                res ^= i;
            }else
                res ^= a[i]; //0只异或数组元素
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一次遍历，最多$n+1n+1$个元素
• 空间复杂度：$O(1)O(1)$，无额外空间使用

方法四：累加运算

具体做法： 我们知道数组中有1到n中的所有数字，多了一个数字x，那我们累加的数组和也比1到n的累加多了数字x。

class Solution {
public:
    int search(int n, vector<int>& a) {
        int suma = 0; //记录数组a的和 
        int sumn = (1 + n) * n / 2; //记录1到n的和
        for(int i = 0; i <= n; i++)
            suma += a[i];
        return suma - sumn; //相减
    } 
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，一共累加$n+1n+1$次
• 空间复杂度：$O(1)O(1)$，无额外空间使用

方法五：快慢双指针

具体做法： 可以把有重复数据的数组看作一个存在环的链表，因此可以使用快慢指针来找到这个环的位置。因为数组长度n+1，数据在[1,n]范围内，因而使用a[a[i]]时，不会越界，且只有一个重复的数，只存在一个环。而且因为下标从0开始，数据中不存在0，所以也不用担心第一个元素会索引到自己，即a[a[i]] = i，不存在这种情况。 慢指针一次性走一步，快指针一次性走两步，相遇则找到了环，环的入口即是重复的元素，再定义一个指针从头开始和慢指针一起一步一步走，相遇的点即是环入口，可以参考一般的环形链表找入口。下图展示怎么将数组视作环形链表：

class Solution {
public:
    int search(int n, vector<int>& a) {
        int slow = 0; //定义快慢指针
        int fast = 0;
        slow = a[slow];
        fast = a[a[fast]];
        while(slow != fast){
            slow = a[slow];
            fast = a[a[fast]];
        }
        int find = 0;
        while(find != slow){
            slow = a[slow];
            find = a[find];
        }
        return slow;
    } 
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，长度为$n+1n+1$的链表，找到环入口最多不会超过$O(n)O(n)$
• 空间复杂度：$O(1)O(1)$，常数级变量

方法六：位置交换法

具体做法： 我们让1到n中每个数对应在数组中0到n-1的位置，遍历数组a，如果对于每个元素如果位置符合则往后，否则需要将这个元素交换到属于它的位置上去，如果那个位置上已经有和它相同的元素了，则找到重复。

class Solution {
public:
    int search(int n, vector<int>& a) {
        int i = 0;
        while(true){
            if(a[i] == i + 1) //符合自己现在的位置
                i++;
            else if(a[i] == a[a[i] - 1]) //要放的位置上的元素已经有这个元素了，说明找到重复数
                return a[i];
            else
                swap(a[i], a[a[i] - 1]); //交换到自己应该去的位置
        }
        return 0;
    } 
};

复杂度分析：

• 时间复杂度：$O(n)O(n)$，最多交换$nn$次即可完成排序，下标最多移动$nn$次即可遍历完数组找到重复
• 空间复杂度：$O(1)O(1)$，常数级变量