[leet code] Two Sum

풀기 전 생각해보기

1. n이 최대 10^3이니 부르트포스로 풀어도 될듯 O(n^2)
2. 두개의 숫자를 더하는데 각 숫자 최대값이 10^9이니 int로 커버 가능

코드

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

결과

통과

다른 방법

map을 사용하여 time complexity O(n)에 풀 수 있다. 대신 매개변수로 주어진 배열 이외에 map을 별도로 사용해야하기 때문에 space complexity 가 O(n)이 된다.

#include <map>
using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> m;
        for(int i=0; i<nums.size(); i++){
            m.insert(make_pair(nums[i],i));
        }
        
        int rest;
        map<int, int>::iterator iter;
        for(int i=0; i<nums.size(); i++){
            rest = target - nums[i];
            iter = m.find(rest);
            if(iter != m.end() && (*iter).second != i){
                return {i, (*iter).second};              
            }
        }
        return {};
    }
};

c++ map 사용법
1) map에 key에 해당하는 value 유무 확인

map<int, int>::iterator iter;
iter = my_map.find(key);
// key에 해당하는 값이 존재한다면, iterator 를 return
// key에 해당하는 값이 존재하지 않는다면, my_map.end()와 같은 값을 return

결과

1번 풀이 결과 (브루트포스)

2번 풀이 결과 (hash table)