Java实现尺取法

同学推荐的一题，看了别人及讲解，学到了一点新的东西------尺取法

例题如下：

Description

A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.

Input

The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

Output

For each the case the program has to print the result on separate line of the output file.if no answer, print 0.

Sample Input

2

10 15

5 1 3 5 10 7 4 9 2 8

5 11

1 2 3 4 5

Sample Output

2

3

自己是真的菜，所有题目拿到的第一反应都是暴力求解，看完别人的才想到有尺取法这么有效的东西。

尺取法

就是像尺一样可以伸长与缩小。

步骤1主要是先初始化左右端点，怎么初始化呢？先是找到符合条件的端点，即从第一个端点开始往后延伸，直到出现符合条件的端点

步骤2就是开始缩减区间的长度，这里重要的判断标准就是，如果条件成立，那就将左端点向右延伸，左端点不动，但是一旦出现条件不成立的情况，就应该将右端点向左延伸，直到条件满足位置，重复此循环直到整个数组都经历过判断后即可，时间复杂度从O(n*n)降到了O(n),非常方便。

import java.util.Scanner;
public class num3061第二版 {
  public static void figure(int []num,int n)
  {
    int sum=0;
    for(int i=0;i<num.length;i++)
      sum+=num[i];
    if(sum<n)
      System.out.println(0);
    else 
    {
      int s1=0,s2=0,res=num.length,sum1=0;
      for(;;)
      {
        while(s1<num.length&&sum1<n)//这里进行初始化左右端点
          sum1+=num[s1++];
        if(sum1<n)
          break;
        res=Math.min(res, s1-s2);//每次结算最小的区间长度
        sum1-=num[s2++];
      }
      System.out.println(res);
    }
  }
  public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    for(int i=0;i<n;i++)
    {
      int m1=sc.nextInt();
      int m2=sc.nextInt();
      int []num=new int [m1];
      for(int j=0;j<m1;j++)
        num[j]=sc.nextInt();
      figure(num, m2);
    }
  }
}