<알고리즘, 백준>투 포인터를 이용한 백준 2003번 수들의 합2 풀이

배열에서 두 개의 포인터를 사용하여 탐색하는 방법.(O(n))

• 1. 같은 방향에서 두 개의 포인터를 배치하여 시작하는 방법.
• 2. 다른 방향(첫번째 원소,마지막 원소)에 각각 포인터를 배치하여 시작하는 방법.
     투포인터를 사용하면 다중 for문(O(n^2))을 선형적으로 풀 수 있다.
     투포인터는 연속적인 값들을 이용해 푸는 문제에 적합하다.

예제 백준 2003번 수들의 합2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        StringTokenizer st2 = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st2.nextToken());
        }

        int sum=0;
        int start=0,end=0,count=0; //start,end를 포인터로 첫번째원소에 같이 배치함.

        while(start < arr.length){ //start가 전체 수열보다 작을동안
            if (sum > m || end == arr.length) {// 총합이 목표값보다 크거나 end가 전체길이에 도달시
				sum -= arr[start++];//총합에 start가 위치한 값 빼고, start 다음 위치로++
			} else { //총합이 목표값보다 작거나 같을경우
				sum += arr[end++];//총합에 end값 더하고, end 다음 위치로++
			}
			if (sum == m) {//총합이 목표값에 도달했을 때
				count++;
            }
        }
        System.out.println(count);
    }
}