공부 기록

연속된 수들 중 부분합이 S 이상인 최소 길이를 구하면 되므로 투 포인터를 활용하여 풀어본다

부분 합이 sum보다 작을 때에는 오른쪽 인덱스를 가리키는 포인터를 오른쪽으로,

sum보다 클 때에는 왼쪽 인덱스를 가리키는 포인터를 오른쪽으로 옮긴다.

부분합의 가장 작은 길이를 구해야 하므로 while문을 돌면서 min 값을 업데이트 해준다.

import java.util.*;
import java.io.*;

public class Main {
	public static int n;
	public static long sum;
	public static int arr[];

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		sum = in.nextInt();
		arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = in.nextInt();
		}

		int leftIndex = 0;
		int rightIndex = leftIndex;
		int ans = n + 1;
		long subSum = arr[leftIndex];
		while (leftIndex <= rightIndex) {
			if (subSum < sum) {
				rightIndex++;

				if (rightIndex == n) {
					break;
				}

				subSum += arr[rightIndex];
			} else if (subSum == sum) {
				ans = Math.min(ans, rightIndex - leftIndex + 1);

				rightIndex++;

				if (rightIndex == n) {
					break;
				}

				subSum += arr[rightIndex];
			} else {
				ans = Math.min(ans, rightIndex - leftIndex + 1);

				subSum -= arr[leftIndex];
				leftIndex++;
			}
		}

		if (ans > n) {
			ans = 0;
		}
		System.out.println(ans);

	}
}