---
title: 1. Two Sum
tags: [leetcode, easy, cpp]
---
# 1. Two Sum
## Description
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 <= 10^4
* -10^9 <= nums[i] <= 10^9
* -10^9 <= target <= 10^9
* **Only one valid answer exists.**
**Follow-up:** Can you come up with an algorithm that is less than O(n^2) time
complexity?
## Solution
```cpp
#include <unordered_map>
#include <utility>
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashmap;
vector<int> ans;
for(int i = 0; i <= nums.size(); i++) {
auto iter = hashmap.find(target-nums[i]);
if(iter != hashmap.end()) {
ans.push_back(iter->second);
ans.push_back(i);
return ans;
}
hashmap.insert(make_pair(nums[i], i));
}
return ans;
}
};
```
## Reference
### [C++ map vs. unordered_map](https://stackoverflow.com/questions/2196995/is-
there-any-advantage-of-using-map-over-unordered-map-in-case-of-trivial-keys)
* `map` keeps its elements ordered
* the efficiency of lookup (O(log n) vs. amortized O(1))
* if the `unordered_map` array grows too large, it will do a rehash of all the
elements
* hash has roughly linear complexity on the length of the key
### [Range-based for loop (since
C++11)](https://en.cppreference.com/w/cpp/language/range-for)
**Example**
```cpp
#include <iostream>
#include <vector>
int main()
{
std::vector<int> v = {0, 1, 2, 3, 4, 5};
for (const int& i : v) // access by const reference
std::cout << i << ' ';
std::cout << '\n';
for (auto i : v) // access by value, the type of i is int
std::cout << i << ' ';
std::cout << '\n';
for (auto&& i : v) // access by forwarding reference, the type of i is int&
std::cout << i << ' ';
std::cout << '\n';
const auto& cv = v;
for (auto&& i : cv) // access by f-d reference, the type of i is const int&
std::cout << i << ' ';
std::cout << '\n';
for (int n : {0, 1, 2, 3, 4, 5}) // the initializer may be a
// braced-enclosed initializer list
std::cout << n << ' ';
std::cout << '\n';
int a[] = {0, 1, 2, 3, 4, 5};
for (int n : a) // the initializer may be an array
std::cout << n << ' ';
std::cout << '\n';
for ([[maybe_unused]] int n : a)
std::cout << 1 << ' '; // the loop variable need not be used
std::cout << '\n';
for (auto n = v.size(); auto i : v) // the init-statement (C++20)
std::cout << --n + i << ' ';
std::cout << '\n';
for (typedef decltype(v)::value_type elem_t; elem_t i : v)
// typedef declaration as init-statement (C++20)
std::cout << i << ' ';
std::cout << '\n';
for (using elem_t = decltype(v)::value_type; elem_t i : v)
// alias declaration as init-statement (C++23)
std::cout << i << ' ';
std::cout << '\n';
```
**Output:**
```
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
0 1 2 3 4 5
1 1 1 1 1 1
5 5 5 5 5 5
0 1 2 3 4 5
0 1 2 3 4 5
```
