# Leetcode Two Sum

#### 2022-06-10

---

##### Data structures:

#DS #array #map #unordered_map

##### Algorithms:

#algorithm

##### Difficulty:

#coding_problem #leetcode #difficulty-easy

##### Related topics:

##### Links:

- [Link to problem](https://leetcode.com/problems/two-sum)
- [O(n) Solution](<https://leetcode.com/problems/two-sum/discuss/13/Accepted-C++-O(n)-Solution/263>)

---

### Problem

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.

#### Examples

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.**

### Thoughts

Firstly, I think up an easy O(n^2) solution, by using a nested loop,
But the best solution utilizes an **[[cpp_std_unordered_map]]**.

> [!tips]
> Use **[[cpp_std_unordered_map | unordered map]]** to create a hash table, it has O(1) in search, delete and insert. #tip

### Solution

O(n^2) solution

```cpp
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
      vector<int> pair;
      for (int i = 0; i < nums.size(); i++) {
        for (int j = i + 1; j < nums.size(); j++) {
          if (nums[i] + nums[j] == target) {
            pair.insert(pair.begin(), i);
            pair.insert(pair.begin(), j);
            return pair;
          }
        }
      }
      return pair;
    }
};
```

O(n) solution

```cpp
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
      // use unordered_map here.
      unordered_map<int, int> umap;
      for (int i = 0; i < nums.size(); i++) {
        auto search = umap.find(target - nums[i]);
        if ( search != umap.end()) {
          return vector<int> {i, search->second};
        }

        umap[nums[i]] = i;
      }
      return vector<int> {0, 0};
    }
};
```
