알고리즘 - 투포인터

1. 개념

• 투포인터는 List에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘 입니다.

• 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때 까지 탐색합니다.

2. 구현방식과 코드예시

• 두 개의 포인터 left와 right는 현재 부분 배열의 시작을 가리키고 있습니다.

• 이 두 포인터를 이용하여 부분 배열의 합을 계산하고, 그 합이 target과 같은지 확인합니다.

• 부분 배열의 합이 target보다 작다면, end 포인터를 오른쪽으로 이동시켜 합을 늘립니다.

• 부분 배열의 합이 target보다 크다면, start 포인터를 오른쪽으로 이동시켜 합을 줄입니다.

• 이와 같은 과정을 반복하면서 target을 찾을 때까지 계속 진행합니다.

• 만약 target을 찾았다면, 해당 부분 배열의 인덱스를 반환하거나 기타 필요한 작업을 수행합니다.

public int[] twoSum(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int currentSum = nums[left] + nums[right];
        
        if (currentSum == target) {
            return new int[] { left, right };
        } else if (currentSum < target) {
            right++;
        } else {
            left++;
        }
    }
    
    return new int[0];
}

3. 시간복잡도

매 루프마다 항상 두 포인터 중 하나는 1씩 증가하고, 각 포인터가 n번 누적 증가해야 알고리즘이 끝납니다. 각각 배열 끝에 다다르는데 O(N)이라 둘을 합해도 여전히 O(N) 입니다.

슬라이딩 윈도우와 차이

둘이 거의 비슷하게 구간을 훓으면서 지나간다는 공통점이 있으나, 슬라이딩 윈도우는 어느 순간에도 구간의 넓이가 동일하다는 차이점이 있습니다.

---

ref.
https://butter-shower.tistory.com/226