DaleStudy | Leetcode Study 1주차 - Two Sum

Leetcode Study

문제

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(n2) time complexity?

 

풀이

 

이 문제는 주어진 배열의 원소 2개를 더해서 target을 만드는 건데, 먼저 브루트포스 방식으로 풀어보면 답을 얻을 수는 있으나 O(n^2) 시간복잡도를 가지게 된다. 하지만 주어진 조건을 보면 시간복잡도와 공간복잡도가 O(n)이여야한다. 

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];
            }
        }
    }

};

 

 

그럼 다른 방식으로 생각해봐야하는데, 한 번의 반복문에서 target에서 현재의 원소를 뺼 때 나머지의 값이 어느 위치에 있는지만 알면 이 문제를 해결할 수 있다. 이 방식으로 풀게 되면 시간복잡도를 O(n)까지 줄일 수 있다. 

function twoSum(nums: number[], target: number): number[] {
    for (let i=0; i<nums.length; i++) {
        const complement = target - nums[i];
        if (nums.includes(complement)) {
            const complementIdx = nums.indexOf(complement);
            return [i, complementIdx];
        }
    }
    return [];
  
};

 

하지만 여기서 문제가 생긴다. 배열이 [3,2,4]가 있고, target이 6인 경우 6-3은 3인데, 3은 배열 0번째에 있기 때문에 리턴이 [0,0]이 되는 상황이 벌어진다. 하지만 우리가 원하는 답은 [1, 2]이다. 이러한 부분을 해결하기 위해서는 객체를 이용하여 이미 방문한 원소를 저장해놓을 수 있다. 

function twoSum(nums: number[], target: number): number[] {
    const visited: {[key: string]: boolean} = {}
    for (let i=0; i<nums.length; i++) {
        const complement = target - nums[i];
        if (visited[complement]) {
            const complementIdx = nums.indexOf(complement);
            return [i, complementIdx];
        }
        visited[nums[i]] = true;
    }
    return [];
};

 

 

이 부분을 자바스크립트 자료구조인 Map을 이용해서도 해결할 수 있다. 객체를 생성하는 부분을 Map으로 생성해서 구현할 수도 있다. 

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

    for (let i=0; i<nums.length; i++) {
        const complement = target - nums[i];
        if (map.has(complement)) {
            return [i, map.get(complement)];
        }
        map.set(nums[i], i);
    }
    return [];
};

 

 

 

 

 

 

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