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

박기영·2023년 8월 24일

LeetCode

목록 보기
14/41

solution

/**
 * @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];
            }
        }
    }
};

가장 간단하게 생각해낼 수 있는 방법이다.
이중 for문을 사용해서 target과 일치하는 합을 찾고, 해당 인덱스를 반환하면 된다.

다른 분의 solution

const twoSum = (numbers, target) => {
    let p1 = 0
    let p2 = numbers.length - 1
    
    while (numbers[p1] + numbers[p2] !== target) {
        if (numbers[p1] + numbers[p2] > target) {
            p2--
        } else {
            p1++
        }
    }
    
    return [p1 + 1, p2 + 1]
}

이 분은 two pointer 알고리즘을 사용하셨다.
맨 앞과 맨 뒤에 포인터를 두고, 그 값들의 합과 target이 일치할 때까지 연산한다.
만약 numbers[p1]target - numbers[p2]보다 크다면 뒤쪽에 있는 포인터를 감소시키고,
그 반대라면 앞쪽에 있는 포인터를 증가시킨다.

예시로 살펴보면 이해가 빠르다.

numbers = [2,7,11,15], target = 9

p1 = 0, p2 = 3, numbers[p1] = 2, numbers[p2] = 15 일 때,
(numbers[p1] > target - numbers[p2]) 이므로 상대적으로 큰 값인 p2를 감소시킨다.

현재 배열은 오름차순으로 되어 있기 때문에,
(numbers[p1] > target - numbers[p2]) 상황이라면,
numbers[p2]가 너무 크다는 뜻이 되기 때문이다.
profile
나를 믿는 사람들을, 실망시키지 않도록

0개의 댓글