[LeetCode] 1. Two Sum

Description

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 <= 104
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists.

My Solution

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
    const map1 = new Map();
    for(let i = 0; i < nums.length; i += 1) {
        if (map1.has(nums[i])) {
            return [map1.get(nums[i]), i]
        }
        map1.set((target - nums[i]), i)
    }
    return []
};

Time complexity

• Best case: O(1)
• Worst case: O(n)
• Average case: O(n)

Space complexity

• Best case: O(1)
• Worst case: O(n)
• Average case: O(n)

Feedback

Brute force

const 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];
            }
        }
    }
    return [];
};

Brute force time complexity

• Best case: O(1)
• Worst case: O(n^2)
• Average case: O(n^2)

Brute force space complexity

• Best case: O(1)
• Worst case: O(1)
• Average case: O(1)

Brute force보다 성능이 좋아진 이유

한 번 읽었던 아이템에 대한 정보를 Map 해시테이블에 저장하고, for과 같은 loop로 인덱스를 돌면서 값들을 비교하는 것이 아니라Map.prototype.has() 메서드로 한 번 읽었던 저장된 정보에 접근해서 O(1)으로 계산했기 때문입니다.

Map.prototype.has()이 O(1)인 이유

키 값은 해시 값을 갖습니다. 해시 값이 인덱싱을 충분히 빠르게 할 수 있도록 적절히 지정되어 있다면, 모든 요소를 돌면서 키 값을 비교할 필요 없이 O(1)의 시간으로 접근할 수 있게 됩니다.

Map.prototype.has() time complexity

• Best case: O(1)
• Worst case: O(n)
• Average case: O(1) for good hash function

Map.prototype.has() space complexity

• Best case: O(1)
• Worst case: O(1)
• Average case: O(1)

Reference

• Linear Probing in Hashing