C++] leetCode 1 - Two Sum

 

 

리트코드 1번 문제

 

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

 

 Example 1: 

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

 

 

Example 2:

• Input: nums = [3,2,4], target = 6
• Output: [1,2]

 

 

Example 3:

• Input: nums = [3,3], target = 6
• Output: [0,1]

 

 

Constraints:

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

 

map<int, int> indices에는 각 숫자와 인덱스를 맵핑해 저장한다.

 

i = 1부터 순회하며 탐색하는데 현재 숫자와 더했을 때 target을 만들 수 있는 숫자가 map에 있는지 찾고 찾은 경우 리턴 벡터에 찾은 숫자 key의 Value인 인덱스와 현재 인덱스를 저장한 뒤 루프를 탈출한다.

 

찾지 못한 경우엔 현재 숫자와 인덱스를 map에 저장한다.

 

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret(2);
        map<int, int> indices;
        indices[nums[0]] = 0;
        for(int i = 1; i < nums.size(); i++) {
            auto it = indices.find(target - nums[i]);
            if(it != indices.end()) {
                ret[0] = it->second;
                ret[1] = i;
                break;
            }            
            indices[nums[i]] = i;
        }

        return ret;
    }
};