LeetCode - two sum

two sum

• Difficulty : easy

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

• 정수 배열이 주어지면, 두 숫자의 합이 target 이 되면 index 를 반환하여라
• 각 입력에는 정확히 하나의 해결책이 있다고 가정할 수 있으며, 동일한 요소를 두 번 사용할 수 없다.

example

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

solution

• 작성 언어 : javascript

// 초기 코드
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    
};

• 2중 for문
• 시간복잡도 중첩 for 문이니 O(n^2)
• leet code runtime 176 ms

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

• hash table
• 키(key) 1개와 값(value) 1개가 1:1로 연관되어 있는 자료구조이다. 따라서 키(key)를 이용하여 값(value)을 도출할 수 있다.
• 시간 복잡도 for 문이 하나이니 O(n)
• leet code runtime 84 ms

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
        
    const hashTable = {};
    let resultNumberArray = [];
    
    for(const [index, num] of nums.entries()) {
        
        const differenceValue = target - num;
       
        if(hashTable[num] != undefined) {
            resultNumberArray = [hashTable[num], index];
            break;
        } else {
            // undefined
            hashTable[differenceValue] = index;
      
        }        
        
    }
    
    return resultNumberArray;
    
};

• key 값이 target - num 값이다. 두 수를 합해서 9라는 수를 만들어야하는데 한쪽 숫자를 빼서 필요한 숫자를 key 로 지정해두는거다.
• Array.entries() 는 javascript의 내장 함수로, 배열의 각 인덱스에 대한 키와 값 쌍을 포함하는 새 Array를 가져온다.
• != undefined 조건에 이렇게 명시를 해줬는데, 이유는 javascript 에 false 한 값들 때문이다. 저 안에 0 값이 들어있으면 그냥 else 로 빠져서 정상동작을 하지 않는다.

false 한 값
undefined
0
-0
'' -> 빈 문자열
null
NaN
false