STL容器带你解题

这题使用STL容器是稳稳能解出来的，vector的写法：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> nums[i];
    }

    // 对数组进行排序
    std::sort(nums.begin(), nums.end());

    long long missing_sum = 0;
    int expected = 1; // 从1开始检查
    for (int i = 0; i < n; ++i) {
        // 检查并累加缺失的数字
        while (nums[i] > expected) {
            missing_sum += expected;
            expected++;
        }
        // 如果当前数字刚好是expected，那么expected增加
        if (nums[i] == expected) {
            expected++;
        }
    }

    // 检查从最后一个数字到k的缺失数字
    while (expected <= k) {
        missing_sum += expected;
        expected++;
    }

    std::cout << missing_sum << std::endl;
    return 0;
}

当然vector的写法有漏洞，接下来我们用set集合，集合是有序的，还能去重，最后用本该出现的减去出现的就是结果，而并非累加（科普一下：等差数列求和公式是（首项+末项）*项数/2），另外考虑输入的数字大于k的情况，代码如下

#include<iostream>
#include<set>
using namespace std;
int main(){
	long long n,k;
	cin>>n>>k;
	set<long long> a;
	for(int i=1;i<=n;i++){
		long long u;
		cin>>u;
        if(u>k) continue;
		a.insert(u);
	}
	long long ans=(1+k)*k/2;
	for(auto &i:a) ans-=i;
	cout<<ans;
	return 0;
}

本段代码的时间复杂度是O（n）
这就是我的思路