[LeetCode] 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.

 

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 <= 10^4

• -10^9 <= nums[i] <= 10^9

• -10^9 <= target <= 10^9

• Only one valid answer exists.

 

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

 

💡 문제해석

이 문제는 정수 배열 nums와 정수 target이 들어 왔을 때, 두 수의 합이 target이 되게 하는 nums 배열의 인덱스를 출력하는 문제이다.

 

 

---

 

🎈문제 풀이

Solution 1. Brute Force

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

이중 for문을 돌리는 단순한 방법으로, loop를 돌리면서 두 수의 합이 target이 될 때 해당 인덱스를 리턴하는 방법이다.

정답으로는 크게 문제가 없지만 최악의 경우 n^2 만큼 동작할 수도 있다.

 

이 경우 시간복잡도를 최소화 하기 위해 hash를 이용하는 경우가 많다고한다.

 

 

Solution 2. Hash Table

var twoSum = function(nums, target) {
    
    const store = new Map();
    
    for (let i = 0 ; i < nums.length; i++) {
        const param = target - nums[i];
        
        if(store.has(param))  return [store.get(param), i];
        store.set(nums[i], i);
    }
    return [];
}

이 방법은 HashMap을 이용하여, 기존의 값을 기억해 놓는 방법이다.

 

① const param = target - nums[i];

target에서 nums의 값을 빼 주어 어떤 수를 더했을 때 target이 될 수 있는지 찾는다.

 

② if (store.has(param)) return [store.get(param), i];

target을 만들 수 있는 param이 store에 존재하는지 확인하고, 존재한다면 그 값을 리턴한다.

 

③ store.set(nums[i], i);

target을 만들 수 있는 param이 store에 존재하지 않는다면, hash에 해당 값을 저장한다.

 

 

👉🏻 Map에 대해 알고싶다면 더보기를 클릭해주세요.

[javascript] Map

 

 

🎈문제 풀어보기

Two Sum - LeetCode