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] <= 1000numbersis sorted in non-decreasing order.-1000 <= target <= 1000- The tests are generated such that there is exactly one solution.
Approach
EN
KR
원티드 프리온보딩 수업에서 들었던 알고리즘 Two Pointers를 이용해서 풀었다.
주어진 배열이 이미 오름차순으로 정렬이 되어있기 때문에 맨 왼쪽, 맨 오른쪽에서부터 범위를 좁혀나가면 된다.
1. 왼쪽 포인터와 오른쪽 포인터를 준다. (배열의 0번째 인덱스: 왼쪽 / 마지막 인덱스: 오른쪽)
2. 왼쪽 포인터가 오른쪽 포인터보다 크지 않을 때까지 while 반복문을 실행하면서 왼쪽과 오른쪽의 합(sum)을 구한다.
3. sum이 타겟의 값보다 크다면 큰 값을 줄여야 되므로오른쪽 포인터를 왼쪽으로 이동하고, sum이 타겟의 값보다 작다면 더 큰 값을 더해줘야 하므로 왼쪽 포인터를 오른쪽으로 이동한다.
code
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
var twoSum = function(numbers, target) {
let left = 0;
let right = numbers.length-1;
let sum;
while(left<right) {
sum = numbers[left]+numbers[right];
if(sum === target) {
return [left+1,right+1];
} else if(sum>target) {
right--;
} else {
left++;
}
}
};Review
사실 제일 좋은 방법으로 풀었기 때문에 놀랄 만큼 다른 사람들의 접근 방식이 비슷했다. 변수명을 좀 다르게 주고 순서만 좀 다른 정도?! 그렇기 때문에 무식하게(?!) 접근하는 방법도 한번 구현해 보기로 했다. 완전탐색으로 모든 가능한 조합을 확인하여 합이 target인 경우를 찾는다. 이 경우 두 개의 반복문을 하기때문에 시간 복잡도는 O(n^2)이 된다.
그동안은 구현을 하는데에 급급했었는데 리뷰를 해보면서 공부하다 보니 반복문 한번 추가가 시간복잡도를 훨씬 안좋게 만들 수 있구나를 깨달았다. 그도 그럴것이 생각해보면 똑같은 배열을 두번 돌아야 하는데, 배열의 길이가 엄청나게 길 경우 굉장히 비효율적이겠다 라고 느꼈다.
code
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
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];
}
}
}
};