[Java] 투 포인터

Reverse Direction

Same Direction

• 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 방법
• 두 개 포인터의 배치 방법
  • 첫 번째 요소에 둘 다 위치 (Same direction pointers)
    • Array에서의 중복 제거, 최소 길이의 합을 찾는 문제가 대표적
    • Array에서의 중복 제거 문제는 Slow, Fast 포인터로 나뉘며 Slow는 unique한 요소를 가리키고 Fast는 중복 체크를 하며 이동
  • 첫 번째 요소와 마지막 요소에 위치 (Reverse direction pointers)
    • 팰린드롬 문자열이 대표적인 문제
• 다중 for문의 복잡도를 좀 더 linear하게 해결할 수 있음

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 3, 7, 2, 4, 3, 2};
        System.out.println(Arrays.toString(twoPointers(arr, 9)));
    }

    public static int[] twoPointers(int[] arr, int target) {
        int p1 = 0, p2 = 0, sum = 0;
        int[] result = {-1, -1};
        while (true) {
            if (sum > target) {
                sum -= arr[p1++];
            } else if (p2  arr.length) {
                break;
            } else {
                sum += arr[p2++];
            }
            if (sum  target) {
                result[0] = p1;
                result[1] = p2 - 1;
                break;
            }
        }
        return result;
    }
}

 

[reference]
https://medium.com/@klintcho/two-pointer-techniques-a-visual-tutorial-9ce2d36a15ed
https://cdragon.medium.com/basics-of-two-pointers-technique-e1a0df57ba7e