[알고리즘] Range: Two Pointer

1. Two Pointer

• 정렬된 선형 자료구조에서 조건을 만족하는 구간/쌍을 찾는 알고리즘 입니다.
• 두 개의 포인터를 동시에 움직여가며 문제를 해결합니다.

 

동작 원리

1. 포인터 설정: 두 개의 포인터 배치 (배열의 시작과 끝)
2. 포인터 이동: 범위를 좁히거나 넓히는 방식. (한쪽 또는 양쪽 모두를 이동시킴)
3. 조건 만족 검사: 두 포인터의 현재 위치에서 조건을 만족하는지 검사

 

코드

int countPairsEqualToM(int[] a, int M) {
    Arrays.sort(a);
    int l = 0, r = a.length - 1, cnt = 0;
    while (l < r) {
        int s = a[l] + a[r];
        if (s == M) { cnt++; l++; r--; }     // 한 쌍 찾음 → 양쪽 이동
        else if (s < M) l++;                 // 더 크게
        else r--;                            // 더 작게
    }
    return cnt;
}

 

장점

• 성능: O(n) (반복을 줄여 시간복잡도를 줄임)

 

2. 문제

Two Sum

• 배열 중 조건을 만족하는 숫자쌍 찾기

 

문제

• Two Sum 2 - Input Array is sorted (문제) (해설)

 

Fast / Slow

• 배열 내 중복 원소 확인하기
• 링크드리스트 내 사이클 확인하기

 

문제

• Linked List Cycle (문제) (해설)

 

 

출처

• [Median] tarun jain - Two Pointers