[LeetCode] 1. Two Sum (Easy) 풀이

❓ 문제

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.

 

정수로 이루어진 배열과 정수인 target이 주어지면, 두 숫자의 합이 target이 된 인덱스를 반환한다.

각각의 입력은 단 하나의 방법이 있다고 가정하며, 같은 배열의 요소를 두 번 사용하지 않도록 한다.

순서 상관없이 return 할 수 있다.

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]

 

❗ 내 풀이

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

Runtime: 256 ms
Memory Usage: 41.8 MB

중첩 for문을 돌아 시간 복잡도가 O(n²) 되어 느렸던 것 같다.

 

❗ Runtime이 가장 빨랐던 답변과 비교

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

'target - 해당 값'을 뺀 다음 그 값을 찾기 위해 hashMap을 사용하였다.

• 'map[키] = 값'으로 map에 값을 넣을 수 있다.
• 'map[키]'를 출력하면 값을 리턴한다.
• '값 in map'을 하면 map 안에 해당 값이 있는지 체크한다.

for문만 사용하지말고 Map을 활용할 수 있는지 파악해보기

has와 in의 차이

어떤 풀이는 'if( diff in map )'을 사용하였고 어떤 풀이는 'if( diff has map )'을 사용하였기에 그 차이에 대해 알고자 간단하게 설명한 사진이다.

https://masteringjs.io/tutorials/fundamentals/hasownproperty

 

❗ Memory 사용이 가장 적었던 답변과 비교

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = (nums, target) => {
    const store = {};
    for(let i = 0; i < nums.length; i++){
        let targetKey = `${target - nums[i]}`
        let key = `${nums[i]}`
        if(store[targetKey]) return [store[targetKey].index, i]
        store[key] = {index: i}
    }
    return null;
}

Runtime이 빨랐던 답변과 같이 Map을 사용하였다. (store변수가 map)

다른 점은 if문에서 in을 사용하지 않고 바로 값이 있는지 확인하는 것과 값으로 '{index: 해당 인덱스}' 객체가 들어가는 것이다. (해당 값이 0일 경우도 있으니 index로 키 값을 준 것 같다.)

 

💡 개선방안 적용 후 내 풀이

Runtime이 가장 빨랐던 풀이와 같다.

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

Runtime: 90 ms
Memory Usage: 42.9 MB

 

🚩 Detail

• 날짜 : 2022.03.10
• 난이도 : Easy
• 제목 : Two Sum
• URL : https://leetcode.com/problems/two-sum/

Two Sum - LeetCode