정렬되어 있지 않은 배열의 두 수 합이 target이 되는 두 요소의 인덱스를 찾는 문제이다.
이중 for문으로 찾을 수 있지만, 문제에는 O(n^2)보다 나은 시간 복잡도라는 조건이 있다.
정렬된 배열의 두 수의 합이 target이 되는 문제는 👉 여기
정렬된 배열에서는 left, right 두 포인터를 이용하여 범위를 좁히는 방법을 사용했었다.
Input: nums = [3,2,4], target = 6
Output: [1,2]
nums 배열을 반복하며 value-index를 map에 저장한다. 이때 value는 target - nums[i]
의 값이다. 만약 target
에서 nums[i]
를 뺀 값이 있으면, 현재 인덱스 i
와 맵에 저장된 temp
의 인덱스를 리턴한다. 시간 복잡도 O(n) / 공간 복잡도 O(n)로 해결할 수 있다.
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const temp = target - nums[i];
if (map.has(temp)) {
return [map.get(temp), i];
}
map.set(nums[i], i)
}
};