3. Two Sum

#leetcode/1

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.

Solution

Solution in C++ with hashmap

We can iterate over the array and find out if we had already saved target - nums[i] in a hashmap. If the answer is yes, we can return the current index and the index we saved in target - nums[i].

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> map;

    for(int i = 0; i < nums.size(); i++) {
        if(map.find(target - nums[i]) == map.end())
            map[nums[i]] = i;
        else
            return { map[target - nums[i]], i };
    }
    
    return {};
}

• Time complexity: $O(n)$ (where n is the size of the vector)
• Space complexity: $O(n)$ (we are storing all the input)