2003번 수들의 합 2 (JAVA)

문제 설명

• 주어진 배열에서 연속된 수들의 합이 특정 값 N이 되는 부분 수열의 개수를 구하는 문제입니다.

입력 설명

• 첫 번째로 주어지는 M은 배열의 크기입니다.
• 두 번째로 주어지는 N은 우리가 찾고자 하는 부분합의 값입니다.
• 이후 M개의 숫자가 배열에 주어집니다.

알고리즘 설명

1. 초기화:
   • 배열에서 두 개의 포인터 left와 right를 사용합니다.
   • left는 현재 부분합의 시작을 가리키며, right는 부분합의 끝 다음을 가리킵니다.
   • sum은 left부터 right-1까지의 부분합을 저장합니다.
   • 초기화 시, left는 0에, right는 1에 위치하며, sum은 첫 번째 원소의 값으로 초기화됩니다.
2. 부분합 탐색:
   • while 루프를 통해 left 포인터가 배열의 끝에 도달할 때까지 반복합니다.
   • 현재 부분합 sum이 N과 같은 경우, cnt를 증가시킵니다.
   • 만약 sum이 N보다 작고, right가 배열의 범위를 벗어나지 않았다면, right를 증가시키고 sum에 새로운 원소를 더합니다.
   • 만약 sum이 N보다 크거나, right가 더 이상 증가할 수 없다면, sum에서 arr[left]를 빼고 left를 증가시킵니다.
3. 결과 출력:
   • 위 과정을 통해 부분합이 N과 같은 경우를 모두 찾았다면, 그 개수를 출력합니다.

import java.util.Scanner;

public class 수들의_합_2 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        int arr[] = new int[M];
        for (int i = 0; i < M; i++) {
            arr[i] = sc.nextInt();
        }

        int left = 0;
        int right = 1;
        int sum = arr[0];
        int cnt = 0;
        while (left < M) {
            if (sum == N)
                cnt++;
            if (sum < N && right < M) {
                sum += arr[right++];
            } else
                sum -= arr[left++];
        }
        System.out.println(cnt);
    }
}