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].
Plain Text
복사
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].
Plain Text
복사
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].
Plain Text
복사
Constraints:
•
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.
My solution
비감소 순서로 정렬되어 있는 numbers 배열이 있다. 두 개의 숫자를 찾아 특정 target 숫자에 합치도록 한다.
이 두 숫자를 1 <= index1 < index2 <= numbers.length 인 numbers[index1] 와 numbers[index2] 라고 한다.
index1 , index2 인 두 숫자의 인덱스를 [index1, index2]로 반환해라.
테스트는 정확히 하나의 솔루션으로 존재하도록 생성되었다. 동일 요소를 두번 쓸 수 없다.
솔루션은 일정 공간만 사용해야 한다.
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].
Plain Text
복사
2,7,11,15가 주어지고 9을 만들기 위한 인덱스 2개를 [index1, index2]로 반환했다.
인덱스 형식은 1부터 시작이다.
이는 투포인터로 찾아야 공간 복잡도를 아낄 수 있다.(주어진 조건)
우선 초기 상태에는 s, e 포인터 둘다 0을 가리키고 부분 배열의 합도 0이다.
이때 부분 배열의 합이 target보다 작다면 end를 증가시킨다.(자연수니까 가능하다.)
target보다 큰 값이 되었으므로 s를 증가시킨다.
(만약 부분 배열의 합이 target보다 큰 값이 되면 s를 증가시킨다.)
s e
2. 7 11 15
이 때 부분 배열의 합은 2가 된다.
하지만 target이 9이므로 부분 배열의 합이 더 작아서 e를 증가시킨다.
s. e
2. 7 11 15
이 때 부분 배열의 합이 9이 된다. target과 같으므로 반복을 종료한다.(early return)
Code
/**
* @param {number[]} numbers
* @param {number} target
* @return {number[]}
*/
const twoSum = function (numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) return [left + 1, right + 1];
if (sum < target) {
left++;
} else {
right--;
}
}
};
describe('twoSum', () => {
it('TC1', () => {
expect(twoSum([2, 7, 11, 15], 9)).toStrictEqual([1, 2]);
});
it('TC2', () => {
expect(twoSum([2, 3, 4], 6)).toStrictEqual([1, 3]);
});
it('TC3', () => {
expect(twoSum([-1, 0], -1)).toStrictEqual([1, 2]);
});
});
JavaScript
복사