C++ 最短连续页数问题：双指针算法详解

问题描述:

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

输入描述:

3 行，第 1 行包含 1 个数字 P, 代表页数的个数 P。

第 2 行包含 P 个数字, 代表教材每页中的知识点 a[i]。

第 3 行包含 1 个数字 K, 代表需要看完的 K 个知识点。

输出描述:

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

思路：双指针

先用一个哈希表记录每个知识点出现的位置，便于后面的查找。
用双指针维护一个区间，使区间内包含所有需要看的知识点。
每次向右移动右指针，直到区间包含了所有需要看的知识点，记录此时的区间长度，并向右移动左指针，缩小区间长度，直到不再包含所有需要看的知识点。在这个过程中，记录每个区间的最小长度，即为所求。

时间复杂度：O(n)

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

int main() {
    int P, K;
    cin >> P >> K;
    vector<int> a(P);
    for (int i = 0; i < P; ++i) {
        cin >> a[i];
    }
    unordered_map<int, int> mp;
    for (int i = 0; i < P; ++i) {
        mp[a[i]] = i;
    }
    int left = 0, right = 0;
    int count = 0;
    int minLen = P;
    while (right < P) {
        if (mp.count(right + 1) && mp[right + 1] < left) {
            left = mp[right + 1];
        }
        if (mp.count(right + 1)) {
            ++count;
        }
        ++right;
        while (count == K) {
            minLen = min(minLen, right - left);
            if (mp.count(left) && mp[left] < right) {
                --count;
            }
            ++left;
        }
    }
    cout << minLen << endl;
    return 0;
}