우리의 임무는 기껏해야 선형 시간에 이합 문제를 해결하는 함수를 작성하는 것입니다.
두 개의 합 문제
정수 배열이 주어지면 특정 대상 숫자에 합산되는 두 개의 숫자를 찾아야 합니다.
twoSum 함수는 대상에 합해지는 두 숫자의 인덱스를 반환해야 하고, 대상에 합해지는 두 요소가 없으면 함수는 빈 배열을 반환해야 합니다.
O(n) 시간에 문제 해결
이미 나타난 항목의 기록을 유지하기 위해 해시맵을 사용할 것입니다. 매 패스마다 지도에 현재 요소에 추가될 때 대상에 추가하는 요소가 있는지 확인합니다. 존재하는 경우 다음을 포함하는 배열을 반환합니다. 이 조건을 만족하지 않고 전체 루프를 돌면 빈 배열을 반환합니다.
예시
const arr = [2, 5, 7, 8, 1, 3, 6, 9, 4];
const sum = 10;
const twoSum = (arr, sum) => {
const map = {};
for(let i = 0; i < arr.length; i++){
const el = sum - arr[i];
if(map[el]){
return [map[el], i];
};
map[arr[i]] = i;
};
return [];
};
console.log(twoSum(arr, sum));
console.log(twoSum(arr, 12));
console.log(twoSum(arr, 13));
console.log(twoSum(arr, 14));
console.log(twoSum(arr, 24)); 출력
콘솔의 출력은 -
[ 2, 5 ] [ 1, 2 ] [ 1, 3 ] [ 3, 6 ] []