[Leetcode] 1. Two Sum - JS

https://leetcode.com/problems/two-sum/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- 정수배열 nums, 정수 target이 주어질 때, 두 숫자를 더해서 target이 되는 index를 반환하라.
- 각 입력에는 정확히 1개의 해답이 있고 동일한 요소를 2번 사용하면 안된다.
- 순서는 상관없다.

제한조건
--------------------
- 2 <= nums.length <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9

 

2. 접근 방법

접근방법
--------------------
인덱스 반환하는 것이므로 오름차순 정렬하면 안됨.
Brute Force로 첫번째 요소 하나에 그 이후 요소 모두 대입하는 방법은 적절하지 않다. 
제한 조건에 시간초과 예상

해쉬 맵 사용

1. num을 key로 해쉬를 만든다. val은 key의 인덱스
2. keys를 순회
	- hash[target - key] 가 존재하면
	- [key의 index, target - key의 인덱스] 반환

 

 

3. 코드

var twoSum = function(nums, target) {
    const numIndexMap = {};

    for (let i = 0; i < nums.length; i++) {
        const num = nums[i];
        const complement = target - num;

        if (numIndexMap.hasOwnProperty(complement)) {
            return [numIndexMap[complement], i];
        }

        numIndexMap[num] = i;
    }
    
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

index를 반환해야 하므로 배열 자체를 정렬하면 안되고, Brute Force 방법을 사용하자니 제한 조건에서 시간 초과가 발생할 것 같았다.

그래서 해쉬 맵을 사용하여 nums 배열의 요소를 key 값으로 하고 value 값은 인덱스로 할당해주었다.

 

(target - num) key 값이 해쉬 맵에 존재하면 그 때의 index들을 반환해준다.

처음에는 중복되는 num 값이 존재하니 index를 담는 배열을 생각했었다.

하지만, 위 문제에서 해답은 유일하게 1개 존재한다고 했으니 3 + 3 = 6과 같은 경우에서 nums에 포함된 '3'은 정확히 2개 뿐일 것이다.

왜냐하면 '3'이 3개라서 nums = [3, 0, 3, 3], target = 6 이면 해답이 [0, 2], [0, 3], [2, 3] 이 될 수 있기 때문이다.

 

그러므로 index 값을 배열로 가지고 있을 이유가 없다. 그저 target - num 을 key로 하는 값을 hash에서 발견하면 target - num 의 index와 현재 요소의 index를 반환해주면 된다.