C++ 最短连续页数算法：双指针法实现知识点覆盖

问题描述:

假设一本教材中有 P 页，每页包含第 a[i] 个知识点，知识点可能会重复。现给出每页的知识点 a[i] 以及需要看的知识点数 K，请你求出能够看完全部 1~K 个知识点的最短连续页数。注意本题必有解，不存在不包含的知识点。

输入描述:

3 行，

第 1 行包含 1 个数字 P, 代表页数的个数 P。
第 2 行包含 P 个数字, 代表教材每页中的知识点 a[i]。
第 3 行包含 1 个数字 K, 代表需要看完的 K 个知识点。

输出描述:

1 行，表示最少连续页数。

思路：双指针法

定义两个指针 left 和 right，分别表示滑动窗口的左右边界，初始值都为 0。然后 right 向右移动，直到窗口中包含了所有需要看的知识点。此时，我们记录窗口大小，然后 left 向右移动，每次移动一格，直到窗口中不包含所有需要看的知识点，再次移动 right，直到包含所有需要看的知识点……以此类推，直到 right 到达最后一页，此时就找到了最短的连续页数。

具体实现时，我们可以用一个 unordered_map 来记录每个知识点出现的次数，然后在移动窗口时，每当将某个知识点加入窗口时，将其对应的出现次数减 1，表示已经有一个该知识点在窗口中了。当某个知识点的出现次数为 0 时，就说明窗口中已经包含了所有该知识点，可以将需要看的知识点数减 1。当需要看的知识点数变为 0 时，就说明窗口中包含了所有需要看的知识点。

时间复杂度：O(n)

空间复杂度：O(n)

参考代码:

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    int P, K;
    cin >> P >> K;
    int a[P];
    for (int i = 0; i < P; i++) {
        cin >> a[i];
    }
    
    unordered_map<int, int> mp;
    int left = 0, right = 0;
    int minLen = P;
    int count = 0; // 记录窗口中包含的知识点数
    
    while (right < P) {
        if (mp[a[right]]++ == 0) {
            count++; // 窗口中出现新的知识点
        }
        
        while (count == K) { // 窗口中包含了所有需要看的知识点
            minLen = min(minLen, right - left + 1); // 更新最小窗口大小
            if (--mp[a[left]] == 0) { // 窗口中不再包含知识点 a[left]
                count--;
            }
            left++;
        }
        right++;
    }
    
    cout << minLen << endl;
    return 0;
}

示例：

输入：

5
1 2 1 3 2
3

输出：

解释：

教材中有 5 页，需要看 3 个知识点。最短的连续页数为 3 页，分别是第 2、3、4 页，包含所有需要看的知识点。