TwoPointer

투포인터 알고리즘 : 배열에서 두개의 Pointer를 기록해 두며 문제를 풀어나가는 방식이다.

기본 아이디어

1. 두 개의 포인터를 설정한다. 하나는 배열의 시작, 하나는 배열의 끝
2. 두 포인터를 조건에 따라 움직인다.

투포인터의 장점

• 일반적으로 시간 복잡도가 O(n)을 가져간다.
• 투 포인터가 배열을 한 번만 훑으면서 지나가기 때문이다.

적용할 수 있는 문제

예제 문제 1 : 두수의 합

문제 설명

주어진 정렬된 배열에서 두 수의 합이 특정 타겟 값이 되는 두 수를 찾는 문제.

입력 : 1, 5, 8, 10, 13, 16 , 27 ,32 ,45 ,60
이렇게 들어올 떄 Target의 인덱스를 찾는 방법은?

public class TwoSum {
    public int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[] {left, right};
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        throw new IllegalArgumentException("No two sum solution");
    }

    public static void main(String[] args) {
        TwoSum solution = new TwoSum();
        int[] nums = {1,5,8,10,13,16,27,32,45,60};
        int target = 40;
        int[] result = solution.twoSum(nums, target);
        System.out.println("Indices: " + result[0] + ", " + result[1]);
    }
}