[알고리즘] LeetCode - Two Sum II - Input Array Is Sorted

Two Sum II - Input Array Is Sorted - LeetCode

문제 설명

• 정수형 배열 numbers가 오름차순 정렬되어 주어진다.
• 두 숫자의 합인 정수형 변수 target이 주어진다.
• numbers에서의 두 수의 합이 target이 되는 두 개의 인덱스를 포함한 정수형 배열을 반환한다.
• target값을 만들 수 있는 두 수가 있는 경우는 하나 이상 주어진다.

문제 해결

• 두 개의 포인터(투포인터)를 통해 양쪽에서 접근한다.
• 포인터로 지목된 두 수의 합이 target보다 크면 뒤쪽 포인터를 하나 줄이고, target보다 작으면 앞쪽 포인터를 하나 늘린다.
• 두 수의 합이 target과 일치할 때 또는 앞 포인터가 뒤 포인터보다 작을 때까지 반복한다.

시간 복잡도

• O(N)
• 정수형 배열 numbers의 크기만큼만 반복하면 되기 때문에 시간 복잡도는 O(N)이다.

유사 코드

앞 포인터 head 선언 후 0으로 초기화
뒤 포인터 tail 선언 후 (numbers길이 - 1)으로 초기화

앞 포인터가 뒤 포인터보다 작을 때까지 반복
	sum = head위치의 값과 tail위치의 값의 합
	sum과 target이 같으면
    	반복문 중지
	sum이 target보다 크면
    	tail--
    sum이 target보다 작으면
    	head++
return [head + 1, tail + 1] 정수형 배열 반환

풀이 코드

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int head = 0;
        int tail = numbers.length - 1;

        while(head < tail) {
            int sum = numbers[head] + numbers[tail];

            if (sum == target) {
                break;
            } else if (sum > target) {
                tail--;
            } else if (sum < target) {
                head++;
            }
        }

        return new int[]{head + 1, tail + 1};
    }
}

결과

시간	메모리
2 ms	45.3 MB