第三场（A2-找卧底）

链接：https://ac.nowcoder.com/acm/contest/6383/A
来源：牛客网

题目描述
牛牛今天和大家玩了一个新游戏，除了牛牛以外还有n个人参加游戏，现在这n个人中的每个人从[1,n]中选择一个数字，保证选出的数字均不重复。牛牛作为第n+1个人，充当卧底的角色，要求卧底从1到n中选择一个数字，现在将n+1个数字重新打乱顺序，请找出卧底选择的数字是多少。

示例1
输入
4,[1,2,1,4,3]
输出
1
备注:
其中1<=n<=100000。
要求时间复杂度为O(n)，额外空间复杂度为O(1)
解题思路
1-n所有数字都出现了一次，卧底的数字多出现一次。遍历数组求和，减去前n个自然数的和即可。
代码

class Solution {
public:
    /**
     * 
     * @param n int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int search(int n, vector<int>& a) {
        // write code here
        int sum = 0;
        for(int it : a) sum += it;
        return sum - n * (n + 1) / 2;
    }
};