尺取法（双指针）

题目大意

给定一个长度为 的正整数序列和一个整数 ，求最短的连续子序列，使其元素和大于等于 。输出最短长度，若不存在则输出 。

解题思路

本题是经典的尺取法（双指针） 应用。由于序列中所有元素均为正整数，满足单调性，可以使用双指针高效求解：

1. 初始化：左右指针 left = 0 和 right = 0，当前子序列和 sum = 0，最小长度 min_len = n + 1（初始设为不可能的大值）。
2. 移动右指针：不断将 a[right] 加入 sum，直到 sum >= S。
3. 移动左指针：当 sum >= S 时，尝试向右移动左指针：
   • 更新最小长度：min_len = min(min_len, right - left + 1)
   • 从 sum 中减去 a[left]，左指针右移
   • 重复直到 sum < S
4. 终止条件：右指针遍历完整个序列后，若 min_len 未被更新（仍为 n+1），说明无解，输出 ；否则输出 min_len。

时间复杂度：，每个元素最多被左右指针各访问一次。
空间复杂度：，存储序列。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n, S;
        cin >> n >> S;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        int left = 0;
        long long sum = 0; // 使用 long long 防止大数溢出
        int min_len = n + 1; // 初始化为不可能的大值

        for (int right = 0; right < n; right++) {
            sum += a[right]; // 扩展右边界
            // 当前和满足条件时，尝试收缩左边界
            while (sum >= S) {
                min_len = min(min_len, right - left + 1);
                sum -= a[left];
                left++;
            }
        }

        if (min_len == n + 1) {
            cout << 0 << '\n';
        } else {
            cout << min_len << '\n';
        }
    }
    return 0;
}

双指针循环：

• 右指针 right 从 到 遍历序列，将元素加入 sum。
• 左指针 left 在 sum >= S 时向右移动，更新最小长度并减少 sum。

关键点

• 正整数序列的单调性：保证了当左指针右移时，子序列和严格递减，不会跳过最优解。
• 边界更新时机：在收缩左指针前更新 min_len，确保记录的是当前满足条件的最短子序列。
• 无解判断：通过初始化 min_len = n + 1，最后检查该值是否被更新。