{"oj":"poj","problem_id":"3061","title":"Subsequence","tags":["双指针"],"md_path":"poj/poj3061.md","url":"/problems/poj/3061","html_content":"
\n

目录

\n
\n

求数字串中连续子序列的最小长度，要求这个子序列的和至少得大于等于S。

\n
cpp
#include <iostream>\nusing namespace std;\nconst int maxn =2e5;  // 数组最大长度\nint a[maxn];          // 存储正整数序列\nlong long n ,s;       // n: 序列长度, s: 目标和\n\nint main (int argc, char *argv[]) {\n    int T;  // 测试用例数量\n    std::cin >> T;\n    while (T--) {\n        std::cin >> n >> s;  // 读取序列长度n和目标和s\n        \n        // 读取序列中的每个正整数\n        for(int i = 1;i <= n ;++i ) // i: 1->n\n        {\n            std::cin >> a[i];\n        }\n        \n        int ans = n+1;    // 答案初始化为不可能的值(n+1)，表示还没找到解\n        int i = 1 ,j = 1; // 滑动窗口的左右指针，初始都指向第一个元素\n\n        long long sum = a[1];  // 当前窗口的和，初始为第一个元素\n        \n        // 滑动窗口主循环，右指针不超过数组边界\n        while( j <= n)\n        {\n            if( sum >=s) {\n                // 当前窗口和>=目标值，尝试更新答案\n                if(ans > j-i+1) ans = j-i+1;  // 更新最小长度\n                \n                // 收缩窗口：移除左边界元素，左指针右移\n                sum -=a[i];\n                i++;\n            }\n            else if( sum < s) {\n                // 当前窗口和<目标值，需要扩展窗口\n                j++;                    // 右指针右移\n                sum +=a[j];            // 加入新元素到窗口和\n            }\n        }\n        \n        // 如果答案还是初始值，说明没找到满足条件的子序列，输出0\n        if( ans == n +1) ans = 0;\n        std::cout << ans << \"\\n\";\n    }\n    return 0;\n}\n\n
\n","md_content":"\n[[TOC]]\n\n求数字串中连续子序列的最小长度，要求这个子序列的和至少得大于等于S。\n\n@include-code(./poj3061.cpp, cpp)\n"}