1. Two Sum 풀이 - js

해당 포스팅은 릿코드 1번 Two Sum 풀이를 다룬다. 문제 링크

---

문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

정수 배열 nums와 정수 target이 주어질 때, 더했을 때 target과 값이 같은 배열의 두 숫자를 찾아, 두 숫자의 index를 배열로 반환하라.

O(n^2)보다 시간복잡도가 작은 풀이가 있을까?

---

예제

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

---

풀이

내가 처음에 푼 풀이는 각 원소와 그 원소의 index를 배열로 저장한 2차원 배열을 만든 다음, 해당 배열을 원소의 값에 대해 정렬 후 투포인터를 이용해 답을 구했다.

// 내 풀이
var twoSum = function(nums, target) {
    const arr = nums.map((n, idx) => [n, idx]);
    arr.sort(([a],[b]) => a-b);
    
    s = 0;
    e = arr.length - 1;
    while (s < e) {
        sum = arr[s][0] + arr[e][0];
        if (sum === target) break;
        
        if (sum > target) e-=1;
        else if (sum < target) s+=1;
    }
    return [arr[s][1], arr[e][1]];
};

이 코드는 시간복잡도는 꽤 괜찮았지만 공간복잡도가 하위 7.23%였다. 세상에...😣

그래서 다른 사람들은 대체 어떻게 풀었을까 하고 릿코드의 discuss를 봤는데 어메이징한 솔루션을 발견해서 그 풀이를 소개하고자 한다.

---

Disscuss solution 로직

• 먼저 빈 객체 vals를 정의한다.

• 그 다음 배열 nums를 loop돌리면서

  • target - 현재원소 nums[i]가 vals에 없으면 vals에 nums[i]: i key-value 쌍을 넣어준다.
  • 있으면 [vals[target-nums[i]], i]를 리턴한다.

즉, target-nums[i]를 메모이제이션한다음 vals에 target-nums[i]가 있으면 해당 값의 인덱스와 i 배열을 리턴하는 것이다.

---

전체 코드

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

  for (let i = 0; i < nums.length; i++) {
    if (target - nums[i] in vals) {
      return [vals[target-nums[i]], i];
    } else {
      vals[nums[i]] = i;
    }
  }
};