4416.缺少的数

给定一个长度为 n−1n−1 的数列 a1,a2,…,an−1a1,a2,…,an−1。

数列中的元素两两不同，且都在 1∼n1∼n 的范围内。

请你计算，1∼n1∼n 中的哪一个数没有在数列中出现过。

输入格式

第一行包含一个整数 nn。

第二行包含 n−1n−1 个整数 a1,a2,…,an−1a1,a2,…,an−1。

输出格式

输出 1∼n1∼n 中没有在数列中出现过的数。

数据范围

前三个测试点满足 2≤n≤102≤n≤10。
所有测试点满足 2≤n≤1052≤n≤105，1≤ai≤n1≤ai≤n。

输入样例：

10
3 8 10 1 7 9 6 5 2

输出样例：

4

暴力题解(空间换时间)：

#include<iostream>
using namespace std;
const int N = 1e+5;
int a[N],book[N];
int n;
int main(){
    cin >> n;
    for (int i = 1 ; i < n ; i ++) {
        scanf("%d",&a[i]);   

            book[a[i]] = 1;

    }
    int flag = 0;
    for (int i = 1 ; i < n  ; i ++){
        if (book[i] == 0){
            flag = 1;
            printf("%d",i);
            break;
        }
    }
    if (flag != 1) printf("%d",n);

    return 0;
}

算法2：
(不明算法) O(n)
等差数列求出 1 ~ n 中每个数的和（等差数列）
依次输入，每次用和减去输入的数字
最后剩下的数字即为答案

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

int main()
{
    int n;
    scanf("%d", &n);

    LL sum = (n + 1ll) * n / 2;
    for (int i = 0; i < n - 1; i ++ )
    {
        int x;
        scanf("%d", &x);
        sum -= x;
    }

    printf("%lld\n", sum);
    return 0;
}

注意这种方法要开 long long ！！！