Two Sum

💬 문제

[문제 링크]

정수 배열 nums, 정수 target
합이 target이 되는 두 요소의 인덱스를 배열에 담아 반환
같은 요소 두번 사용 불가, 답은 무조건 하나

✍️ 나의 풀이

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    let map = new Map();

    for (let i = 0; i < nums.length; i++) {
        let num = target - nums[i];
        if (map.has(num))
            return [map.get(num), i];
        map.set(nums[i], i);
    }
};

nums를 순회하면서 target에서 본인을 뺀 값이 map에 있다면
그 value(인덱스)와 본인 인덱스 함께 반환
없다면 map에 숫자-인덱스로 저장
답이 무조건 하나 존재하므로 기본 반환값은 두지 않았음

📌 결과

Accepted
Runtime 56ms (Beats 80.04%)
Memory 51.00MB (Beats 36.82%)

📚 러닝 포인트

two pointer 문제를 풀 때 똑같은 문제가 있었어서 그걸 활용해야 하나? 싶었는데 다시 보니까 그건 정렬이 되어있는 배열이었고, 이 문제에 정렬을 적용해버리면 인덱스 값이 바뀌어서 불가능했다. 그러면 easy 문제이기도 하니 그냥 브루트포스로 가야하나? 생각했다가 hashmap 문제라는 걸 다시 되새겼다. 그래서 target - nums[i]를 map에서 찾아야된다는 키포인트는 잡아서 구현하긴 했는데 나는 처음에 for문으로 map에 모두 넣어놓고 시작했었다. 결과를 보고 좀 더 찾아보니까 굳이 그렇게 안하고 없으면 집어넣고 넘어가는 식으로 해도 되더라. 어차피 답은 하나 꼭 존재하기 때문에 뒤에서 답을 발견해도 된다. 그리고 메모리 비트를 높여보려고 이것저것 했는데 브루트포스로 푼 사람들이 메모리 효율이 잘 나오는 거라서 포기했다.