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

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.

Idea:

Here we construct a lookup map where the key is the number and the value is the index.

Then for search, we compute the corresponding number using (b = target - a).

If this result is present in lookup, we can return the current index and index in lookup map.

Solution:

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> valueToIndex;
        vector<int> res;

        for (int i = 0; i < nums.size(); ++i) {
            valueToIndex[nums[i]] = i;
        }

        for(int i = 0; i < nums.size(); ++i) {
            auto match = valueToIndex.find((target - nums[i]));

            if (match != valueToIndex.end() && i != match->second) {
                res = {i, match->second};
                break;
            }
        }
        return res;
    }
};

Complexity Analysis:

Time

Creating the lookup map is an O(N) operation.

Searching the pair that sums to target is worst case an O(N) operation.

O(N) + O(N) = 0(N)

Memory

Lookup map is O(N)

Result vector is constant space

O(N) + c = O(N)