[Leetcode] 167. Two Sum II - Input Array Is Sorted - JS

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 분석

문제분석
--------------------
오름차순 정렬된 1-index 정수 배열이 주어지면 
특정 목표 숫자(target)에 합산되는 2개의 숫자를 [index1, index2] 반환하라.
O(1)의 공간복잡도를 사용하여 풀어라.

target = numbers[index1] + numbers[index2]
1 <= index1 < index2 <= numbers.length

제한조건
--------------------
- 2 <= numbers.length <= 3 * 10^4
- -1000 <= numbers[i] <= 1000
- numbers는 오름차순 정렬됨
- -1000 <= target <= 1000
- 테스트는 정확히 1개의 해결책이 있도록 생성된다.

 

2. 접근 방법

접근방법 - Two pointer
--------------------
1. index1을 시작, index2를 끝 인덱스에서 시작한다.
2. index1 < index2를 만족하면 반복한다.
    - sum이 target 보다 작으면, index1을 오른쪽으로 이동시킨다.
    - sum이 target 보다 크면, index2를 왼쪽으로 이동시킨다.
    - sum이 target이랑 같으면 [index1, index2]를 반환한다.

 

 

3. 코드

var twoSum = function(numbers, target) {
    let index1 = 0;
    let index2 = numbers.length - 1;
    while (index1 < index2) {
        let sum = numbers[index2] + numbers[index1]
        if (sum < target) {
            index1++;
        } else if (sum > target) {
            index2--;
        } else {
            return [index1 + 1, index2 + 1]
        }
    }
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

Two pointer를 활용했는데, 처음엔 index1, index2를 시작 지점에 두고 하니 효율성이 떨어지고 엣지케이스들이 발생하였다.

가령, numbers = [-1,-1,-1,-1, ..., -1, 1, 1] , target = 2 일 경우 index1, index2를 왼쪽에서 부터 시작 하게되면

불필요한 연산을 많이 하여 시간 초과 에러가 발생한다.

 

Two pointer를 양쪽에서 시작하도록 초기화하여 이를 개선하였다.