[c++/LeetCode-Hash Table] 1. Two Sum

 

 

 

 

난이도: Easy

키워드: Stack

 

 

문제

 

정수 배열 nums와 정수 target이 주어졌을 때, 두 숫자의 합이 target이 되도록하는 숫자의 인덱스를 반환합니다.
각 입력에는 정확히 하나의 해결책이 있다고 가정할 수 있으며, 동일한 요소를 두 번 사용할 수 없습니다.
어떤 순서로든 답을 반환할 수 있습니다.

 

문제 원문: https://leetcode.com/problems/two-sum/description/

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

 

문제 풀이

O(n) 시간 안에 문제를 풀기 위해서, array의 iteration을 도는 동안 답에 해당하는 값을 조회할 수  있도록 할 수 있다.

이를 위해서 Hash Table을 사용할 수 있다. 현재 값과의 합이 target이 되는 값을 찾는 것이 목표이기 때문에 key 값을 array 값으로 하고, 현재 값에 대응되는  key 값이 hash 에 존재하는지 여부를 통해 문제를 해결할 수 있다.

 

#include <unordered_map>
#include <vector>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        // key (int), value (int)
        unordered_map<int, int> hash;
        vector<int> ans;

        for(auto i=0; i < nums.size(); ++i){
            const auto ptr = hash.find(target - nums[i]);
            if(ptr != hash.end()){
                ans.emplace_back(i);
                ans.emplace_back(ptr -> second);
                return ans;
            }
            hash.insert({nums[i], i});
        }
        return ans;
    }
};