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;
    }