题意分析

题目描述了一个女孩Jessica需要在教科书中找到一个最短的连续部分，使得这部分包含书中出现的所有不同的知识点。每个知识点用一个非负整数ID表示，每一页对应一个知识点。目标是找到满足条件的最短连续页数范围。

输入：

• 第一行：书的页数 ( P )（( 1 \leq P \leq 10^6 )）
• 第二行：( P ) 个非负整数，表示每一页的知识点ID

输出：

• 一个整数，表示包含所有不同知识点的最短连续部分的页数

示例：

• 输入：

  5
  1 8 8 8 1
  

• 输出：

  2
  

  解释：最短的满足条件的连续部分是 8 1（第4页和第5页），包含所有知识点（1和8）。

解题思路

这道题目可以转化为经典的**滑动窗口（Sliding Window）**问题，即寻找包含所有不同元素的最短连续子数组。具体步骤如下：

1. 统计所有不同的知识点：

   • 使用 set 存储所有知识点ID，统计不同知识点的数量 ( k )。

2. 滑动窗口寻找最短子数组：

   • 使用双指针（left 和 right）维护一个窗口，并用 map 记录窗口内每个知识点的出现次数。
   • 初始化窗口：right 指针向右扩展，直到窗口内包含所有 ( k ) 个知识点。
   • 优化窗口：left 指针尝试向右收缩窗口，同时保持窗口内仍然包含所有知识点。
   • 更新最短长度：在每次调整窗口时，记录当前窗口的最小长度。

3. 时间复杂度分析：

   • 遍历数组统计不同知识点：( O(n) )
   • 滑动窗口遍历：( O(n) )
   • 总时间复杂度：( O(n) )，适用于 ( n \leq 10^6 ) 的大数据量。

标准代码（优化版）

#include <cstdio>
#include <unordered_set>
#include <unordered_map>
using namespace std;

int xl[1000005]; // 存储知识点ID

int main() {
    int n;
    scanf("%d", &n);
    unordered_set<int> unique_ideas; // 存储所有不同的知识点
    for (int i = 0; i < n; i++) {
        scanf("%d", &xl[i]);
        unique_ideas.insert(xl[i]);
    }
    int k = unique_ideas.size(); // 不同知识点的数量

    unordered_map<int, int> freq; // 记录当前窗口内各知识点的出现次数
    int left = 0, min_len = n; // 初始化窗口左指针和最小长度

    // 滑动窗口遍历
    for (int right = 0; right < n; right++) {
        freq[xl[right]]++; // 扩展右边界

        // 如果当前窗口已包含所有知识点，尝试收缩左边界
        while (freq.size() == k) {
            min_len = min(min_len, right - left + 1); // 更新最小长度
            freq[xl[left]]--; // 左边界右移
            if (freq[xl[left]] == 0) {
                freq.erase(xl[left]); // 如果某个知识点出现次数降为0，从map中移除
            }
            left++;
        }
    }

    printf("%d\n", min_len);
    return 0;
}

代码解析

1. 统计不同知识点：

   • 使用 unordered_set 存储所有知识点ID，自动去重。
   • k = unique_ideas.size() 表示不同知识点的总数。

2. 滑动窗口优化：

   • freq 记录当前窗口内各知识点的出现次数。
   • right 指针扩展窗口，left 指针收缩窗口。
   • 当 freq.size() == k 时，说明窗口已包含所有知识点，此时尝试收缩 left 指针以寻找更小的窗口。

3. 边界处理：

   • 如果某个知识点的出现次数降为0，从 freq 中移除，确保 freq.size() 正确反映窗口内的知识点数量。

4. 输出最短长度：

   • 最终 min_len 即为包含所有知识点的最短连续部分的页数。

总结

• 算法：滑动窗口（Sliding Window）
• 时间复杂度：( O(n) )，适用于大规模数据。
• 空间复杂度：( O(n) )，用于存储知识点和频次统计。
• 关键点：利用哈希表动态维护窗口内的知识点覆盖情况，确保高效计算最短子数组。