[Leetcode/TS] 1. Two Sum

문제

https://leetcode.com/problems/two-sum/description/

 

---

1. 그냥 풀어보자

function twoSum(nums: number[], target: number): number[] {
    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]
            }
        }
    }
};

 

for 문으로 순회하면서 모든 요소들을 다 찾아보고 있으니까 당연히 최선의 방법이 아니다.

그런데 무슨 방법이 있는지 모르니까 일단 이렇게 했다!

얘처럼 모든 경우의 수를 구하는 방법을 부르트 포스라고 한다.

2중 for 문으로 돌기 때문에 시간복잡도가 O(n^2)이다.

 

 

 

 

 

 

다른 방법은 Solutions 를 봤다

2. HashMap 사용

function twoSum(nums: number[], target: number): number[] {
    const hash = new Map<number, number>

    for (let i = 0; i < nums.length; i++) {

        if(hash.has(target - nums[i])) {
            return [hash.get(target - nums[i]), i]
        }

        hash.set(nums[i], i)
    }
};

 

리스트에 내가 원하는 값이 있는지 찾는게 중점이라고 생각하고

처음부터 순회를 하되 map 에 이 조건을 만족하는 값이 있다면 바로 반환, 없다면 인덱스와 함께 값을 넣어준다.

1번씩만 돌아가도 값을 찾아내므로 시간복잡도는 O(n)이다.



 

Testcase

twoSum([3, 2, 4], 6);

// { hash: Map(1) { 3 => 0 } }
// { hash: Map(2) { 3 => 0, 2 => 1 } }

 

 

 

 

 

 

---

너무 오랜만에 해서 바보가 된 기분이다.