LeetCode 1번 Two Sum

---

문제 링크

Two Sum - 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]
Output: 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]

---

풀이

이 문제는 주어진 배열에서 두 개의 원소를 더하여 Target이 되는 값을 찾으면 되는 문제입니다.

해당 문제의 풀이 과정은 크게 2가지로 되어 있습니다.

 

1. 브루트 포스 ( 느림 )

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {

        for (int i = 0; i < nums.size(); i++)
        {
            for ( int j = i + 1; j < nums.size(); j++ )
            {
                if ( nums[i] + nums[j] == target )
                {
                    return {i, j};
                }
            }
        }
        return {};
    }
};

Time Submitted	Status	RunTime	Memory
07/25/2021 14:25	Accepted	312 ms	10.1 MB

시간 복잡도 : O(N^2)

 

2. 해시를 이용 ( 빠름 )

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        map<int, int> dict;

        for (int i = 0; i < nums.size(); i++)
        {
            if (dict.find(target - nums[i]) == dict.end())
            {
                dict[nums[i]] = i;
            }
            else
            {
                return { i, dict[target - nums[i]] };
            }
        }
        return {};
    }
};

Time Submitted	Status	RunTime	Memory
07/25/2021 14:25	Accepted	8ms	10.1ms

시간 복잡도 : O(N)