第三场（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;
}
};
