LeetCode

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

okonomiyakki 2023. 8. 28. 02:46
728x90

[LeetCode Top Interview 150] 문제 설명

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 < numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.

요약

오름차순으로 정렬 되어져 있는 numbers 배열의 요소들 중,

 

두 개 요소의 합이 target 값과 같은 인덱스를 배열로 반환한다.


인덱스는 1부터 지정한다.

My Code

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;
    let answer;

    while (left < right) {
        if (numbers[left] + numbers[right] === target)
            return (answer = [left + 1, right + 1]);
        else if (numbers[left] + numbers[right] > target) right--;
        else left++;
    }
    return answer;
};

투포인터로 left는 시작 인덱스, right는 끝인덱스를 가리키고 while 문을 돌린다.


만약 각 인덱스가 가리키는 numbers 배열 요소의 합이 target 값과 일치하면 해당 인덱스를 1 씩 증가시킨 값을 배열로 반환하여 함수를 종료한다.


target 보다 큰 값이라면 해당 배열이 오름차순으로 정렬되어 있기 때문에 상대적으로 큰 값을 가리키는 right 값을 1 만큼 감소 시킨다.


반대로 target 보다 작은 값이라면 left 값을 1 만큼 증가 시킨다.

  • 문자열의 앞과 뒤에서 동시에 출하여 중간에서 종료되는 반복문이기 때문에 O(n/2)의 시간이 소요된다.

따라서 전체 시간 복잡도는 O(n)이다.

728x90