尺取法课堂笔记(这个笔记是针对最短子序列这道题目)

一、算法核心思想

尺取法本质是双指针技术，通过左右两个指针（l为左指针，r为右指针）框选一段连续区间，根据区间是否满足条件动态移动指针，高效求解“连续区间相关问题”（如本题的“和≥m的最短区间长度”）。

核心逻辑分两种情况：

1. 当当前区间（[l, r]）满足条件时：记录最优解（如区间长度），并向右移动左指针（l++），尝试缩小区间找更优解。
2. 当当前区间（[l, r]）不满足条件时：向右移动右指针（r++），扩大区间范围，直至区间满足条件。

二、代码逐段解析

1. 头文件与宏定义

#include<bits/stdc++.h>  // 万能头文件，包含常用STL库
#define int long long   // 将int类型重定义为long long，避免数据溢出
const int N = 1e6 + 10; // 定义数组最大容量（1e6+10），适配题目数据规模
using namespace std;    // 启用std命名空间，简化代码（无需重复写std::）

2. 变量声明

int n, m, a[N], s[N], ans = 1e9; 
// n：数组元素个数；m：目标区间和的最小值
// a[N]：存储原始数组；s[N]：存储前缀和数组（用于快速计算区间和）
// ans：初始化答案为极大值（1e9），后续更新最小值

3. 主函数流程

（1）输入数据与前缀和初始化

signed main() {  // 因#define int long long，主函数用signed避免编译警告
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];                  // 输入第i个元素
        s[i] = s[i - 1] + a[i];       // 前缀和公式：s[i] = 前i个元素的和
    }

（2）双指针循环（核心逻辑）

    int l = 1, r = 1;  // 初始化左右指针，均从第一个元素开始
    while (l <= n && r <= n) {        // 指针不越界时循环
        int sum = s[r] - s[l - 1];    // 用前缀和快速算区间和：[l, r]的和
        if (sum >= m) {               // 情况1：区间和满足条件（≥m）
            ans = min(r - l + 1, ans); // 更新最短区间长度（当前长度vs已有答案）
            l++;                      // 左指针右移，尝试缩小区间
        } else {                      // 情况2：区间和不满足条件（<m）
            r++;                      // 右指针右移，尝试扩大区间
        }
    }

（3）输出结果

    if (ans == 1e9) cout << 0;  // 若ans未更新（无满足条件的区间），输出0
    else cout << ans;           // 否则输出最短区间长度
    return 0;
}

三、算法关键总结

1. 时间复杂度：O(n)。每个元素仅被左右指针各遍历1次，无嵌套循环。
2. 适用场景：求解“连续区间的最值问题”（如最短/最长区间、和满足条件的区间等），且数组元素非负（保证指针移动后区间和单调变化，无需回退）。
3. 易错点：
   • 前缀和数组从i=1开始初始化，避免i=0时的边界计算错误。
   • 答案初始值需设为极大值（如1e9），确保能被有效更新；最终需判断是否存在有效区间（避免输出初始极大值）。

四、示例辅助理解

假设输入：n=5, m=11，a=[1,2,3,4,5]

• 前缀和s=[0,1,3,6,10,15]
• 指针移动过程：
  1. l=1, r=1：sum=1 <11 → r=2
  2. l=1, r=2：sum=3 <11 → r=3
  3. l=1, r=4：sum=10 <11 → r=5
  4. l=1, r=5：sum=15 ≥11 → ans=5，l=2
  5. l=2, r=5：sum=14 ≥11 → ans=4，l=3
  6. l=3, r=5：sum=12 ≥11 → ans=3，l=4
  7. l=4, r=5：sum=9 <11 → r=6（越界），循环结束
• 最终输出ans=3（对应区间[3,5]，和为12）