[LeetCode] 1. Two Sum

Question :
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
Input: 38
Output: 2
Explanation: The process is like: 3 + 8 = 11, 1 + 1 = 2.
             Since 2 has only one digit, return it.Question
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]
Output: 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 <= 105
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Solution.h

#include<iostream>
#include<vector>
#include<map>

class Solution
{
private:
    int input_target;
    int contains;
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target);
    int getTarget();
    std::vector<int>& inputData();
    void outputData(std::vector<int> data);

};

Solution.cpp

#include "Solution.h"

std::vector<int> Solution::twoSum(std::vector<int>& nums, int target)
{
    std::vector<int> output_data;
    /* time over
    for (int loop_i = 0; loop_i < nums.size(); loop_i++) {
        for (int loop_j = loop_i + 1; loop_j < nums.size(); loop_j++) {
            if ((nums[loop_i] + nums[loop_j]) == target) {
                output_data.push_back(loop_i);
                output_data.push_back(loop_j);
                return output_data;
            }
        }
    }
    output_data.push_back(-1);
    */
    std::map<int, int> two_sum_map;
    for (int loop_i = 0; loop_i < nums.size(); loop_i++) {
        contains = target - nums[loop_i];
        if (two_sum_map.find(contains) == two_sum_map.end()) {
            int temp = nums[loop_i];
           two_sum_map.insert(std::pair<int,int>(temp,loop_i));
        }
        else {
            output_data.push_back(two_sum_map.find(contains)->second);
            output_data.push_back(loop_i);
            break;
        }
        
    }
    return output_data;
}

int Solution::getTarget()
{
    std::cout << "target data : ";
    std::cin >> input_target;
    return input_target;
}

std::vector<int>& Solution::inputData()
{
    int input_data=0;
    input_target = 0;
    std::vector<int>* input_vector;
    input_vector = new  std::vector<int>();
    std::cout << "[exit input -1]" << std::endl;
    while (1) {
    
        std::cout << "input data : ";
        std::cin >> input_data;
        if (input_data == -1) {
            break;
        }
        else
            input_vector->push_back(input_data);
    }
    return *input_vector;
}

void Solution::outputData(std::vector<int> data)
{
    std::vector<int>::iterator iter;
    std::cout << "output data : ";
    for (iter = data.begin(); iter != data.end(); iter++) {
        std::cout << *iter <<" ";
     }
    std::cout << std::endl;
}

* map 사용 안하고 한 경우 Time Over 발생

Result :

Runtime: 292 ms, faster than 34.21% of C++ online submissions for Two Sum.
Memory Usage: 74.9 MB, less than 5.05% of C++ online submissions for Two Sum.

Git Hub : github.com/Anchangun

Anchangun - Overview