• 题目简述：
  • 给定 N 个正整数序列（10 < N < 100 000），每个正整数小于或等于 10000，并给出一个正整数 S（S < 100 000 000）。编写一个程序来查找序列中连续元素的子序列的最小长度，其总和大于或等于 S。

意思就是在一个数列中 找到一个最短的连续子序列，使其Sn恰好是大于给定的S的

  1. 那么我们可以采用双指针的方法
  2. 左指针l 用作for循环中 一次往右移动一下
  3. 右指针r 在while循环中:while(r <= n && sum < s)
  4. 这两个指针的移动形似蚯蚓
  5. 每一次for循环都要更新minlen和当前和sum的值

有两个注意的点：

  1. 由于题目输入的t可能大于1 所以新的轮次开始前要清空数组 memset(a,0,sizeof(a))
  2. minlen更新是if(sum >= s)的情况下才更新，不然循环跳出来有可能是r > n了，但sum并没有>s
using namespace std;
int a[100010];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--) //循环a次
    {
        int n,s;
        scanf("%d%d",&n,&s);
        memset(a,0,sizeof(a));
        for(int i = 1; i <= n; i++)
        {
            scanf("%d",&a[i]);
        }
            int sum = 0, r = 0; //r为右指针 l为左指针
            int minlen = n+1; //minlen的初始化值要总数n都大
            for(int l = 1; l <= n; l++)
            {
                while(r <= n && sum < s)
                {
                    r++; //r指针不断右移
                    sum += a[r];
                }
//                 cout<<l<<" "<<r<<" "<<sum<<endl;
                //while循环结束后 r所处的位置就是我们本次循环找到的临界位置
                if(sum >= s) //当sum大于s时 才更新minlen 
                	minlen = min(minlen, r-l+1);
                //当左指针l向右移动一位时 相应的sum就要减去这个数值
                sum -= a[l];
               
            }
        if(minlen > n) cout<<0<<endl;
        cout<<minlen<<endl;
    }
}

运行结果模拟：

alt