[LeetCode] Two Sum - Javascript

Two Sum

[배열의 두 요소를 더한 인덱스 리턴]

제약 조건 

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
Only one valid answer exists.

 

Example

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

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

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

초기 문제 접근 방식

두 가지 방법으로 문제를 풀이했다.
첫 번째는 이중 반복문을 사용해 배열의 i와 j가 타겟과 같다면 해당 두 개의 인덱스를 리턴했다.
다만 이렇게 풀이하면 시간 복잡도가 O(n^2) 나오기에 효율적인 방법은 아니다.

초기 전체코드

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    for(let i=0; i<nums.length-1; i++) {
        for (let j=i+1; j<nums.length; j++) {
            if (nums[i]+nums[j] === target){
                return [i, j]
            }
        }
    }
};

다시 생각 해보며..

Input: nums = [2,7,11,15], target = 9

해시의 특성을 이용해 먼저 obj 객체를 생성하고 반복문을 수행한다.
반복문을 돌며 another 변수에 target과 nums[i] 뺀 값을 넣는다. (ex. 7, 2, -4, -6)
그 후 obj 객체에 nums[i]의 키로 넣고 value는 i를 넣는다 ex) 2:0, 7:1, 11:2, 15:3
i가 1일 때 obj 객체에는 {2:0} 값을 가지고 있고, another의 값은 2이므로 if 문에 true 조건에 걸려,
현재 obj의 2의 키값을 가진 값 "0"과 i인 1을 리턴해 풀이가 된다.

solve 전체 코드

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
   const obj = {};

   for (let i = 0; i < nums.length; i++) {
      const another = target - nums[i];

      if (another in obj) {
         return [obj[another], i];
      }
      obj[nums[i]] = i;
   }
};