투 포인터

투포인터 알고리즘 동작 흐름

배열에서 두 지점을 가리키는 포인터를 만들어 배열을 검색하는 알고리즘이다. 투 포인터를 사용하는 주된 이유는 시간복잡도를 낮추기 위함이다.
투 포인터 알고리즘에서 포인터 2개를 배치하는 방식에 2가지 경우가 있다.

1) 두 포인터가 배열의 시작과 끝에서 마주보며 진행하는 경우
2) 두 포인터가 배열의 시작에서 같이 방향으로 진행하는 경우

1) 두 포인터가 배열의 시작과 끝에서 마주보며 진행하는 경우

N개의 원소를 가진 배열 arr에서 합이 M인 경우를 찾는다고 해보자. (N, M은 정수)

하나의 포인터는 배열의 첫번째 원소, 나머지 포인터는 배열의 마지막 원소를 가리킨다.
두 포인터는 서로 마주 보며 이동한다. 두 포인터가 만나거나, 가리키는 원소의 합이 M이 될 때까지 이동한다.

1) 배열을 오름차순으로 정렬해준다.
2) 두 원소의 합이 M보다 작으면 왼쪽 포인터를 오른쪽으로 이동시킨다.
3) 두 원소의 합이 M보다 크면 오른쪽 포인터를 왼쪽으로 이동시킨다.
4) 두 원소의 합이 M이면 그 때의 값을 저장하고 왼쪽 포인터를 오른쪽으로, 오른쪽 포인터를 왼쪽으로 이동시킨다.
5) 두 포인터가 만날 때까지 위 과정을 반복한다.

2) 두 포인터가 배열의 시작에서 같이 방향으로 진행하는 경우

N개의 원소를 가진 배열 arr에서 연속된 인덱스 i~j까지의 합이 M이 되는 경우를 찾는다고 해보자. (배열의 원소는 자연수)
대표적인 문제로 boj 2003 수들의 합 2 문제를 한 번 보자. https://www.acmicpc.net/problem/2003

시작점을 가리키는 포인터를 start, 끝 점을 가리키는 포인터를 end, 포인터가 가리키는 두 원소의 합을 sum, 찾고자 하는 경우의 갯수를 cnt라고 하자.

1) 두 원소의 구간합이 M이면 구하고자 하는 경우를 찾았으니 cnt를 1 더해준다. start가 가리키는 원소의 값을 sum에서 빼주고 start를 1 더해준다. end를 1 더해주고 더해진 end가 가리키는 원소의 값을 sum에 더해준다.
2) 두 원소의 구간합이 M보다 작으면 end를 1 더해주고 더해진 end가 가리키는 원소의 값을 sum에 더해준다.
3) 두 원소의 구간합이 M보다 크면 start가 가리키는 원소의 값을 sum에서 빼주고 start를 1 더해준다.
4) end가 N이 될 때까지 위 과정을 반복한다.

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

public class Main
{
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n+1];

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

        int cnt = 0, start = 0, end = 0, sum = arr[0];

        while (true)
        {
            if (sum == m)
            {
                sum -= arr[start++];
                sum += arr[++end];
                cnt++;
            }
            else if (sum < m)
                sum += arr[++end];
            else if (sum > m)
                sum -= arr[start++];

            if (end == n)
                break;
        }

        bw.write(Integer.toString(cnt));
        br.close();
        bw.flush();
        bw.close();
    }
}