NC107658 POJ3061 Subsequence

题目要求找到长度最小的子串，使得字串和大于等于S
既然是要长度最小，那我们就可以从长度为1开始遍历到长度为N
，我们需要遍历次 ，当N非常大的时候耗时会特别长，所以可以稍微优化一下（双指针/尺取法）。

如果是按长度从1到N遍历，那么我们每次都要从子串的头到尾重新计算一次子串和，对此我们可以做出这样的优化：
按数组元素的位置遍历，从第一个元素开始，从长度为1不断修改子串的长度，直到子串和刚好大于等于S，再从第二个元素开始，继续往下遍历

#include <iostream>
#include <vector>

using namespace std;

vector<int> nums;   //输入的数字序列
int main() {
    int t;  // number of test cases
    int N, S;
    cin >> t;
    while (t-- > 0) {
        nums.clear();
        int temp;
        int minLength = 1e5;    //满足题意的最小长度
        cin >> N >> S;
        for (int i = 0; i < N; ++i) {
            cin >> temp;
            nums.push_back(temp);
        }

        int i = 0, j = 0, sum = nums[0], length = 1;    //用于对数组的遍历
        if (nums[0] >= S) {
            cout << 1 << endl;
            continue;
        }
        //length用于记录当前子串长度
        while (j < N && i <= j) {
            if (sum < S) {
                j++;
                sum += nums[j];
                length++;
            } else {
                if (length < minLength)minLength = length;
                sum -= nums[i];
                i++;
                length--;
            }
        }
        //没有答案则输出0
        if (minLength == 100000)cout << 0 << endl;
        else cout << minLength << endl;
    }
}