[leetCode/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.

입출력 예

Example 1:

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

 

Example 2:

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

 

Example 3:

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

Constraints

• 2 <= nums.length <= \(10^4\) 
• 1 <= s.length <= \(10^4\) 
• \(10^9\) <= nums[i] <= \(10^9\)
• \(10^9\) <= target <= \(10^9\) Only one valid answer exists.

---

내 솔루션

• 순간적으로 어짜피 O(n^2) 라고 생각하고 그냥 했다.

var twoSum = function(nums, target) {
  for(let i = 0; i < nums.length; i++) {
    for(let j = 0; j < nums.length; j++) {
      if(i !== j && nums[i] + nums[j] === target){
        return [i, j];
      }
    }
  }
};

최고의 솔루션

• O(n) 솔루션이 있길래 매우 감탄!
• target - nums[i] 를 찾는게 목표라는 점을 간과 했다.

var twoSum = function(nums, target) {
  let hash = {};
  for(let i = 0; i < nums.length; i++) {
    const n = nums[i];
    if(hash[target - n] !== undefined) {
      return [hash[target - n], i];
    }
    hash[n] = i;
  }
}

감상평

• 똑똑이는 세상에 많다. 많이 푸는 수 밖에 없어 보인다.