[LeetCode] 1. Two Sum 풀이

0. 문제

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

주어진 배열 요소 두개의 합이 타겟과 일치할 시 해당 배열의 두 인덱스를 반환한다.

#1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
#2
Input: nums = [3,2,4], target = 6
Output: [1,2]
#3
Input: nums = [3,3], target = 6
Output: [0,1]

 

 

1.언어

자바스크립트(JavaScript)

 

2. 문제 풀이

2-1. 중첩 반복문 - 단순 비교

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

Runtime: 201 ms, faster than 19.81% of JavaScript online submissions for Two Sum.

Memory Usage: 42 MB, less than 95.37% of JavaScript online submissions for Two Sum.

간단하게 반복 문 두개로 단순비교로 작성했더니 런타임 하위 19퍼가 나왔다.

 

2-2.  IndexOf

var twoSum = function(nums, target){
    let arr=new Array(nums.length), index;
    for (let i=0; i<nums.length; i++){
        index = arr.indexOf(target-nums[i])
        if (index !== -1) return [index,i]
        arr[i]=nums[i]
    }
};

Runtime: 203 ms, faster than 19.38% of JavaScript online submissions for Two Sum.

Memory Usage: 43.1 MB, less than 33.34% of JavaScript online submissions for Two Sum.

 

indexOf를 사용해서 다시 풀어보니 똑같이 하위 19퍼가 나왔다.

indexOf 시간 복잡도를 검색해보니 O(n)......  봤던 거 같은데... 복습를 열심히 하자

 

2-3  key :  value 활용

var twoSum = function(nums, target){
  map={};
  for (let i=0; i<nums.length; i++){
    const anr = target-nums[i];
    if (anr in map) return [map[anr],i];
    map[nums[i]]=i;
  }
}

Runtime: 91 ms, faster than 77.47% of JavaScript online submissions for Two Sum.

Memory Usage: 42.4 MB, less than 66.76% of JavaScript online submissions for Two Sum.

드디어 77.47..... key : value의 시간 복잡도는 O(1)이라고 한다.

나는 무슨 문제든 풀 때 배열로 해결하려드는 경향이 심한데 앞으로 key : value 를 자주 활용하자.