1. Two Sum

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

Two Sum - LeetCode

 

정수 목록이 주어졌을 때, 목록 내 두 정수의 합이 목표 값이 되는 경우 그 목록의 인덱스를 반환하는 문제다.

 

[C++]

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> cache;
        
        for (int i = 0; i < nums.size(); ++i)
        {
            int sub = target - nums[i];
            
            auto iter = cache.find(sub); 
            if (iter != cache.end()) {
                return vector<int> { iter->second, i };
            }
            else {
                cache[nums[i]] = i;
            }
        }
        
        return vector<int>();
    }
};

 

[Python3]

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        cache = {}
        for i, value in enumerate(nums):
            remaining = target - nums[i]            
            if remaining in cache:
                return [i, cache[remaining]]
            else:
                cache[value] = i