[백준 1806] 부분합

 

배열의 부분합을 투포인터 기법으로 찾아낸다.

투포인터가 언제나 최소길이의 합을 사용하므로 sum >= s 만 비교해주면 된다.

최초에 초기화한 최소 길이에 변화가 없다면 0을 출력해준다.

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int s = sc.nextInt();
        
        int a[] = new int[n];
        for(int i=0; i<n; i++)
            a[i] = sc.nextInt();
        
        int min = Integer.MAX_VALUE;
        int lo = 0;
        int hi = 0;
        int sum = 0;
        while(true) {
            if(sum >= s) {
                sum -= a[lo++];
                min = Math.min(min, hi-lo+1);
            } else if(hi == n) break;
            else sum += a[hi++];
        }
        System.out.println(min == Integer.MAX_VALUE ? 0 : min);
    }
}