[Leetcode Top Interview 150] 167. Two Sum II - Input Array Is Sorted

난이도 : medium

문제링크

• numbers라는 오름차순 정렬 int 배열이 주어짐
• 두 수의 합이 target이 되는 인덱스 쌍을 리턴해라
• numbers의 원소들은 모두 유니크함

 

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• -1000 <= target <= 1000

 

1. 접근법

• 배열이 오름차순으로 정렬되어 있으므로
  • 투포인터로 두 수의 합이 target보다 작다면 -> 합을 늘려야 함
    • 왼쪽 포인터를 오른쪽으로 한칸 이동
  • 투포인터로 두 수의 합이 target보다 크다면 -> 합을 줄여야 함
    • 오른쪽 포인터를 왼쪽으로 한칸 이동

 

2. 의사코드

int 처음부터_시작하는_포인터 = 0;
int 맨뒤에서_시작하는_포인터 = numbers.length-1;

while (처음부터_시작하는_포인터 < 맨뒤에서_시작하는_포인터) {
	if (numbers[처음부터_시작하는_포인터] + numbers[맨뒤에서_시작하는_포인터] == target) {
    	return [처음부터_시작하는_포인터, 맨뒤에서_시작하는_포인터]
    } else if (numbers[처음부터_시작하는_포인터] + numbers[맨뒤에서_시작하는_포인터] > target) {
    	맨뒤에서_시작하는_포인터--;
    } else {
    	처음부터_시작하는_포인터++;
    }
}

 

3. 구현 코드

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

        while (left < right) {
            if (numbers[left] + numbers[right] == target) {
                break;
                
            } else if (numbers[left] + numbers[right] > target) {
                right--;
            } else {
                left++;
            }
        }

        return new int[]{left+1, right+1};
    }
}

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - n개 원소까지 반복하므로
• 공간복잡도 : O(1) - n개 원소를 돌아도 반복문 안에서 선언되는 변수는 없으므로 상수값만 메모리에 잡힘

5. 개선점

잘 모르겠다

58%, 48%인지...

 

6. 회고

블로깅을 해도 다 이렇게 풀었다.

상위 %가 안좋은 이유도 찾아보니 gc 작업을 해주어야 한다고 한다