[LeetCode] Two Sum II - Input Array Is Sorted - Javascript

Two Sum II - Input Array Is Sorted

[정렬된 number 배열, 더했을 때 target과 같은 배열의 숫자 리턴하기]

 

제약 조건 

2 <= numbers.length <= 3 * 10^4
-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.

Example

ex1) 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].

ex2) 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].


ex3) 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].

문제 접근 방식

투포인터 기법을 사용해 배열 인덱스의 가장 왼쪽과 가장 오른쪽을 더 해 그 숫자가 target보다 크다면 right의 값을 하나씩 빼고,

더 작다면 left의 값을 1씩 증가해 비교하는 방법을 생각했다.

 

number의 배열은 정렬되어 있기에 가능한 방법이다.

만약 number[left]와 number[right]를 더한 값이 target과 같다면 left와 right의 값을 1씩 더해 리턴해 문제를 풀었다.

 

// left는 0 right는 number 배열 길이에 -1을 한 값을 지정한다.
let left = 0;
let right = numbers.length - 1;

 

// numbers[left] 값과 number[right]의 값을 더 해 target 값 보다 크다면 number[right]의 인덱스를 1씩 감소시키고 더 작다면 1씩 증가시킨다.
if (numbers[left] + numbers[right] > target) {
         right--;
      } else if (numbers[left] + numbers[right] < target) {
         left++;
         // number[left]와 number[right] 값을 더 해 target과 같다면 리턴한다.
      } else {
         return [left + 1, right + 1];
      }

전체코드

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

   for (let i = 0; i < numbers.length; i++) {
      if (numbers[left] + numbers[right] > target) {
         right--;
      } else if (numbers[left] + numbers[right] < target) {
         left++;
      } else {
         return [left + 1, right + 1];
      }
   }
};

 

 

다른 sovle 코드

var twoSum = function (numbers, target) {
   for (let i = 0; i < numbers.length - 1; i++) {
      for (let j = i + 1; j < numbers.length; j++) {
         if (numbers[i] + numbers[j] === target) {
            return [i + 1, j + 1];
         }
      }
   }
};

brute focre로도 풀이가 가능하다.
이중 for 문을 돌려 number[i]와 number[j]를 더 해 target과 같다면 해당 i와 j를 1씩 더해 반환하는 것이다.
시간 복잡도가 O(n^2) 나오기에 효율은 좋지 않지만, 더 좋은 복잡도가 생각나지 않는다면 이런 식으로 먼저 풀이하는 것 또한 좋을 방법이라고 생각한다.