假设一本教材中有P页,每页包含第a[i]个知识点,知识点会有所重复,现给出每页的知识点a[i]以及需要看的知识点数K,请你求出能够看完全部1~K个知识点的最短连续页数是多少。注意本题必有解,不存在不包含的知识点。C++
时间: 2024-02-11 16:08:05 浏览: 50
可以使用双指针来解决这个问题。具体来说,我们维护两个指针 l 和 r,表示当前连续的页数为 [l,r]。初始时,l=1,r=0。
然后,我们不断地将 r 右移,直到包含了所有的 k 个知识点。此时,我们更新答案,并将 l 右移,直到不满足包含所有 k 个知识点。然后,我们再将 r 右移,如此往复,直到 r 到达末尾。
代码如下:
```c++
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
unordered_map<int, int> cnt;
int l = 1, r = 0, ans = n + 1;
while (r <= n) {
while (r <= n && cnt.size() < k) {
r++;
cnt[a[r]]++;
}
if (cnt.size() == k) {
ans = min(ans, r - l + 1);
}
while (cnt.size() == k) {
cnt[a[l]]--;
if (cnt[a[l]] == 0) {
cnt.erase(a[l]);
}
l++;
}
}
cout << ans << endl;
return 0;
}
```
时间复杂度为 O(n),空间复杂度为 O(k)。