[4월 2일] Two Sum

문제 : 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.

 

제한 사항

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109

입출력 예

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

Output: [0,1]

Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

풀이 1

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

• 중첩 for문으로, 가장 기본적인 풀이

 

풀이 2

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

• 성능이 확실히 개선됨
• 이중 for문이 아닌, for문을 2개 돌림
• 첫 for문에서는 arr객체에 현재 값:index을 넣음
• 둘째 for문에서는 arr[target-nums[i]]를 통해 key값을 통해 더하면 target이 있는지 값을 구함 -> object의 hash 테이블 이용(object의 값 찾는 속도는 O(1)임)

풀이 3

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

• 성능이 2번 풀이와 성능 차이는 없어보이나, for문 하나로 단번에 해결함

 

---

느낀 점

항상 성능을 어떻게 개선할 수 있는 지도 고려하도록 하자. 그리고, 어떤 자료구조를 사용할 지도 항상 생각하자. 이에 따라 코드의 길이와 질이 달라진다. 자료구조가 어떤 게 있는지 한 번 짚고 넘어가야지.