[003][해시][코알못의 도전기]two sum

Two Sum의 제목을 가진 ... 어디서 많이 풀어본듯한 문제지만 

역시 코알못이기에 .... 코알못들이 많이 푸는 방법으로 풀뻔하였으나 역시 풀지 못함 ... 생각한 시간은 15분정도 ?? 

 

모를 때는 빨리 넘어가기

leetCode는 시간복잡도 및 공간복잡도를 고려해서 단계별로 답안이 있다 ...와우 

 

코알못을 읽으시는 여러분들은 모두 저보다 뛰어나신 분들이실거예요 ...

 

제가 하면 ... 여러분은 더더더더 잘 할 수 있어요!!!!

 

[문제]

 

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

 

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

 

---

[정답] 사실 시간복잡도 및 공간복잡도는 잘 생각을 안했는데 ... 공부해야할 필요성을 느꼈다.

 

Approach 1: Brute Force (무차별 대입!!)

Algorithm

The brute force approach is simple. Loop through each element xx and find if there is another value that equals to target - xtarget−x.

 

Complexity Analysis

• Time complexity: O(n2). For each element, we try to find its complement by looping through the rest of the array which takes O(n) time. Therefore, the time complexity is O(n2).
• Space complexity: O(1). The space required does not depend on the size of the input array, so only constant space is used.

 

    /**
     * @param {number[]} nums
     * @param {number} target
     * @return {number[]}
     */
    var twoSum = function(nums, target) {
        for (let i = 0; i < nums.length; i++){
            for(let j = i + 1; j < nums.length; j++){
                if(nums[j] === target - nums[i]){
                    return [i,j];
                }
            }
            // In case there is no solution, we'll just return null
            return null;
        }
    };

 

---

Approach 2: Two-pass Hash Table

 

Intuition

To improve our runtime complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to get its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.

We can reduce the lookup time from O(n)O(n) to O(1)O(1) by trading space for speed. A hash table is well suited for this purpose because it supports fast lookup in near constant time. I say "near" because if a collision occurred, a lookup could degenerate to O(n)O(n) time. However, lookup in a hash table should be amortized O(1)O(1) time as long as the hash function was chosen carefully.

Algorithm

A simple implementation uses two iterations. In the first iteration, we add each element's value as a key and its index as a value to the hash table. Then, in the second iteration, we check if each element's complement (target - nums[i]target−nums[i]) exists in the hash table. If it does exist, we return current element's index and its complement's index. Beware that the complement must not be nums[i]nums[i] itself!

 

Complexity Analysis

• Time complexity: O(n). We traverse the list containing nn elements exactly twice. Since the hash table reduces the lookup time to O(1), the overall time complexity is O(n).
• Space complexity: O(n). The extra space required depends on the number of items stored in the hash table, which stores exactly nn elements.

Table

 

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        // In case there is no solution, we'll just return null
        return null;
    }
}

 

이걸 js로 어떻게 바꾸는지 아시는분 ..?

---

Approach 3: One-pass Hash Table

Algorithm

It turns out we can do it in one-pass. While we are iterating and inserting elements into the hash table, we also look back to check if current element's complement already exists in the hash table. If it exists, we have found a solution and return the indices immediately.

 

• Time complexity: O(n). We traverse the list containing nn elements only once. Each lookup in the table costs only O(1) time.
• Space complexity: O(n). The extra space required depends on the number of items stored in the hash table, which stores at most nn elements.

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