Two Sum I - Input Array Is Unsorted

1. Two Sum

문제

정렬되어 있지 않은 배열의 두 수 합이 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)
  }
};