[알고리즘] 투포인터(Two pointers)

개념

• 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 활용하여 중복 연산을 줄이는 알고리즘이다.
• 반복적으로 탐색함으로써 O(N^2)이상 걸릴 수 있는 시간 복잡도를 O(N) 으로 줄일 수 있다.

 

구현 방법

• [1, 2, 3, 2, 5] 라는 리스트에서 연속된 수의 합이 5인 경우를 찾아야 할 때를 가정한다면,

    public static int twoPointer() {
        int start = 0; 
        int end = 0;
        int sum = 0;
        int count = 0;

        while (true) {

            if (end == n) break;

            if (sum == m) {
                count++;
                sum = sum + arr[++end] - arr[start++];
            }
            else if (sum < m) {
                sum += arr[++end];
            }
            else {
                sum -= arr[start];
                start++;
            }
        }

        return count;
    }