[LeetCode] 1. Two Sum

[LeetCode] 1. Two Sum

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

풀이1

• Brute-Force 방법

#include <algorithm>

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int size = nums.size();
        for(int i = 0; i<size;++i){
            for(int j = i+1;j<size;++j){
                if(nums[i]+nums[j] == target){
                    return vector<int>{i,j};
                }
            }
        }
        return vector<int>{-1,-1}; //no answer
    }
};

풀이2

• 더 빠른 풀이
• 이전에 비슷한 유형의 문제를 풀며 이 방법을 배웠다
  종종 사용하게 될 것 같으니 잘 기억해두면 좋을 것 같다

• 원래는 map을 이용해서 풀었었는데, 다른 사람의 풀이를 보고 unordered_map을 사용하는 것이 더 빠르다는 것을 알게 되었다

#include <algorithm>
#include <unordered_map>

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //<target-nums[index], index>
        unordered_map<int, int> m;

        int size = nums.size();
        for(int i = 0; i<size;++i){
            //a+b = target
            //b = target-a
            int a = nums[i];
            if(m.find(a) != m.end()){
                return vector<int>{m[a],i};
            }
            else{ 
                m[target-a] = i;
            }
        }

        return vector<int>{-1, -1}; //no answer
    }
};