Two-sum

leet code / top_interview / easy 부터 풀어보기로 했습니다.

문제 링크
https://leetcode.com/problems/two-sum/

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

처음에 작성한 코드입니다. 간단하게 이중 for문을 돌면서 정답을 찾습니다
8
1 2 3 4 6 8 이면,

1 2 / 1 3 / 1 4 / 1 5 / 1 8
2 3 / 2 4 / 2 5 / 2 6 --정답!
으로 돌아가기 때문에 복잡도가 O(n^2)이 나와 시간이 오래걸린 모습입니다.

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

시간 복잡도를 O(n)으로 만들기 위해서 hash 테이블을 이용해보았습니다.
8
1 2 3 4 6 8 이면,

m = { }, m[1]을 탐색
m = { [7,1] }, m[2]를 탐색
m = { [7,1], [6,2] }, m[3]을 탐색
m = { [7,1], [6,2], [3,4] }, m[4]을 탐색
m = { [7,1], [6,2], [3,4], [4,3] }, m[6]을 탐색 성공!
이런식으로 작동하면서 for문을 1개만 쓸 수 있어 복잡도가 O(n)으로 떨어집니다.

시간이 많이 단축되었고, 메모리는 조금 더 쓴 모양새입니다.
아무래도 hash 테이블을 사용하다보니 메모리가 더 사용된 것 같습니다.