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

###### Solution

For each item i in the given array, we need to know whether there is an item j (j < i) such that a[i] + a[j] = target.

Use a hashmap m int -> int to store a mapping from **value** to **index**, so for each a[i], we only need to check m[target - a[i]] exist in the hashmap.

Runtime complexity: O(n)

```
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
vector<int> res;
for(int i = 0; i < nums.size(); i++) {
int remain = target - nums[i];
if (m.find(remain) != m.end()) return { i, m[remain] };
m[nums[i]] = i;
}
return res;
}
```