악명 높은 Two Sum 문제. (DSA 시리즈 3)

문제

정수 nums의 배열과 정수 target이 주어지면 두 숫자의 인덱스를 반환하여 합계가 target이 되도록 합니다.
각 입력에 정확히 하나의 솔루션이 있다고 가정할 수 있으며 동일한 요소를 두 번 사용할 수 없습니다.
어떤 순서로든 답변을 반환할 수 있습니다.

예시

입력: 숫자 = [2,7,11,15], 대상 = 9

출력: [0,1]

설명: nums[0] + nums[1] == 9이므로 [0, 1]을 반환합니다.

입력: 숫자 = [3,2,4], 대상 = 6

출력: [1,2]

입력: 숫자 = [3,3], 대상 = 6

출력: [0,1]

해결책

항목이 정렬된 경우에만 작동합니다

.

배열의 시작(낮음)을 가리키는 포인터와 배열의 끝(높음)을 가리키는 두 개의 포인터가 있습니다.

낮음 < 높음,

낮은 값과 높은 값의 합 = 목표인 경우 인덱스 반환

하한 값과 상한 값의 합 > 목표인 경우 상한 지수를 1 줄임

하한 값과 상한 값의 합 < 목표인 경우 하한 값을 1씩 증가시킵니다.

function twoSum(array, target){
    let low = 0;
    let high = array.length - 1;

    while (low < high) {
        const sum = array[low] + array[high];
        if (sum === target) return [low, high];
        if (sum > target) high--;
        else if (sum < target) low++;
    }
}

방법 2

/**
 * 
 * Input: nums = [2,7,11,15], target = 9 
 * Output: [0,1]
 * Initialize a map,
 * loop through array, 
 * subtract currentItem from target to get compliment, 
 *  if compliment exist in map, return [currentItmIdx, compliment[]]
 * else add map[curentItem] = idx
 * @param {*} array 
 * @param {*} target 
 */
function twoSumMethod2(array, target){
    const map = {};

    for (let i = 0; i < array.length; i++) {
        let com = target - array[i];
        if(map[com] !== undefined) return [i, map[com]]
        else map[array[i]] = i;
    }
    return -1
}

테스트 예

상수 숫자 = [2,7,11,15], 대상 = 9;
상수 숫자 = [3,3], 대상 = 6

-

어쨌든 이 문제를 더 잘 해결할 수 있는 방법이 있다면 댓글에 솔루션을 추가할 수 있습니다. 나는 전문가가 아니다. 소리내어 배우기만 하면 됩니다.

좋아요, 공유 및 댓글 남기는 것을 잊지 마세요. :)