题解：丢失的数据

题目分析

在这个问题中，我们需要从一个丢失了部分数据的序列中，找出 1 到 $k$ 之间缺失的数字，并计算这些缺失数字的和。

已知 $n$ 是数据集中保存下来的数字个数，而数据的范围本应是 $1$ 到 $k$。任务是通过分析现有数据，找出缺失的数字并计算它们的和。

解题思路

1. 数学公式：

   • $1$ 到 $k$ 的所有整数的和可以通过公式计算：
     [
     S = \frac{k \times (k + 1)}{2}
     ]
   • 该公式是常见的求 1 到 $k$ 连续自然数和的公式。

2. 处理数据：

   • 将传输后的数据集中，属于 $1$ 到 $k$ 范围内且没有重复出现的数字累加起来，记为 $q$。
   • 最终的答案就是 $S - q$，即总和减去序列中存在的数字的和。

3. 细节处理：

   • 序列中的数字可能会重复出现，但根据题目要求，每个数字只取一次，这就需要用一个哈希表（unordered_map）来记录哪些数字已经出现过。
   • 我们只处理数据集中 $1$ 到 $k$ 范围内的数字，超出范围的数字无需考虑。

4. 时间复杂度：

   • 我们使用一个哈希表来标记已经出现的数字，这样每个数字只处理一次，整体时间复杂度为 $O(n)$，可以满足 $n$ 最大为 $2 \times 10^5$ 的要求。

AC代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;

// 计算1到x的和
ll sum(ll x) {
    return (1 + x) * x / 2;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    ll n, k, a;
    cin >> n >> k;
    
    // 计算1到k的和
    ll s = sum(k);
    ll q = 0;  // 保存现有数据的和
    
    // 使用哈希表记录已出现的数字
    unordered_map<ll, int> vis;
    
    // 遍历保存的数据集
    for (int i = 0; i < n; i++) {
        cin >> a;  // 输入数据
        
        // 仅当数字在1到k之间，且未出现过时，才累加
        if (!vis[a] && a >= 1 && a <= k) {
            q += a;  // 累加该数字
            vis[a] = 1;  // 标记该数字已出现
        }
    }
    
    // 输出缺失的数字之和
    cout << s - q << endl;
    
    return 0;
}