문제 링크

Explore - LeetCode

문제 설명

배열과 타겟 넘버가 주어지면 배열에서 2개의 원소를 골라 타겟 넘버가 되는 인덱스가 무엇인지 리턴하는 문제이다.

문제 풀이

문제 제목은 굉장히 단순해보이지만 당연하게도 O($n^2$)은 시간초과로 해결할 수 없다. 따라서 2중 반복문으로는 해결할 수 없기에 다른 해결 방법을 찾아봐야한다. 단 2개만을 뽑을 수 있다는 것이 핵심이었다. 배열의 원소들을 Map 에 저장하고 배열을 반복문을 통해 target - i번째 원소 가 Map 에 있는지 확인하는 방식으로 해결하였다.

나의 코드

var twoSum = function (nums, target) {
  const map = new Map();
  nums.forEach((num, idx) => map.set(num, idx));
  for (let i = 0; i < nums.length; ++i) {
    const idx = map.get(target - nums[i]);
    if (idx && i !== idx) return [i, idx];
  }
  return [];
};

if (idx && i !== idx) 를 해주지 않으면 자신을 또 선택할 수 있기 때문에 처리를 해주어야 한다.

다른 사람의 코드

var twoSum = function(nums, target) {
    let map = new Map();
    
    for (let i = 0; i < nums.length; i++) {
        let val = nums[i];
        let diff = target - val;
        
        if (map.has(val)) {
            return [map.get(val), i];
        }
        
        map.set(diff, i);
    }
};

반복문을 한번만 돌려서 체크를 하면서 값을 map에 저장하면 시간을 더 단축할 수 있다.