LeetCode - Two Sum

문제 파악

받은 배열에서 두 수를 더해서 타겟이 되는 서로 다른 두 인덱스를 찾는 문제
이중 for문으로 간단하게 풀 수 있는 문제지만, 투포인터라는 개념을 활용하여 풀어보려고 한다.

투포인터란 배열에서 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는 알고리즘(일반적으로 정렬되어 있을 때 사용)
왼쪽 끝이 시작 포인터, 오른쪽 끝이 끝 포인터
이 때 조건에 따라 왼쪽과 오른쪽 포인터를 이동시키며 결과를 도출
만약 왼쪽이 오른쪽을 넘어간다면 실패

풀이

1. 원래의 인덱스를 보존해야 하기 때문에 [값, 인덱스] 형태의 이차원 배열을 생성
2. 생성한 이차원 배열을 값 기준으로 정렬
3. 투포인터 지정
4. 투포인터로 탐색 시작
   a. 만약 두 값을 더한 값이 타겟보다 작으면 왼쪽 포인터를 이동
   b. 크면 오른쪽 포인터 이동
   c. 타겟과 같으면 반환
5. 만약 타겟과 같은 값이 안나온다면 -1, -1 반환

코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //값, 인덱스 형태의 원래 인덱스 보존 이차원 배열
        int[][] arr = new int[nums.length][2];
        for (int i=0; i<nums.length; i++) {
            arr[i][0] = nums[i]; //값
            arr[i][1] = i; //인덱스
        }

        //arr을 값 기준으로 오름차순 정렬
        Arrays.sort(arr, (o1, o2) -> o1[0] - o2[0]);

        //투 포인터 지정
        int start = 0;
        int end = nums.length - 1;

        while (start < end) {
            //두 값의 합이 target보다 작으면 start를 오른쪽으로 이동
            if (arr[start][0] + arr[end][0] < target) {
                start++;
            } 
            //두 값의 합이 target보다 크면 end를 왼쪽으로 이동
            else if (arr[start][0] + arr[end][0] > target) {
                end--;
            }
            //같으면 원래 인덱스 반환
            else {
                return new int[] {arr[start][1], arr[end][1]};
            }
        }
        //target과 같은 값이 안나오면 실패
        return new int[] {-1, -1};
    }
}