subsequence.java

PKU中一些数据结构基本算法题的java实现

package PKU;
import java.util.Scanner;

/**
 * ID:3061
 * @author yhm
 *
 */
public class Subsequence {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		int caseNum = cin.nextInt();
		for (int i = 0; i < caseNum; i++) {
			int N = cin.nextInt();
			int S = cin.nextInt();
			int[] seq = new int[N+1];
			for (int j = 0; j < N; j++) {
				seq[j] = cin.nextInt();
			}
			int r = solve(seq, N, S);
			System.out.println(r);
		}

	}

	static int solve(int[] seq, int size, int S) {

		int sum = 0;
		int min = Integer.MAX_VALUE;
		int i = 0, j = 0;
		while (j <= i && i <= size) {

			if (sum < S) {
				sum += seq[i];
				i++;
			}
			if (sum >= S) {
				if (i - j < min)
					min = i - j;
				sum -= seq[j];
				j++;
			}
		}
		if(min==Integer.MAX_VALUE)
			return 0;
		else{
			return min;
		}

	}
}