Two Sum easy

Problem Statement

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.

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]

Steps

1. Create a hash map (unordered_map in C++): This map will store each number in nums as a key and its index as the value.
2. Iterate through the array nums: For each number num in nums:
   • Calculate the complement needed to reach the target ( complement = target - num).
   • Check if the complement exists as a key in the hash map.
     • If it exists, it means we found the pair. Return the indices (the current index and the index stored in the hash map for the complement).
     • If it doesn't exist, add the current num and its index to the hash map.
3. If the loop completes without finding a pair, it means no such pair exists (this shouldn't happen according to the problem statement). Return an empty vector or handle the error appropriately.

Explanation

The hash map provides efficient lookups (O(1) on average). Instead of checking every possible pair (which would be O(n^2)), we only need to iterate through the array once (O(n)). For each number, we check if its complement exists in the hash map in O(1) time. Therefore, the overall time complexity is dominated by the single iteration through the array.

Code

#include <vector>
#include <unordered_map>

class Solution {
public:
    std::vector<int> twoSum(std::vector<int>& nums, int target) {
        std::unordered_map<int, int> numMap; // Use unordered_map for efficient lookups

        for (int i = 0; i < nums.size(); ++i) {
            int complement = target - nums[i];
            if (numMap.count(complement)) { // Check if complement exists in the map
                return {numMap[complement], i}; // Return indices
            }
            numMap[nums[i]] = i; // Add current number and its index to the map
        }

        return {}; // Should not reach here according to problem statement.  Handle error as needed.
    }
};

Complexity

• Time complexity: O(n), where n is the length of the input array nums. We iterate through the array once. Hash map lookups are on average O(1).
• Space complexity: O(n) in the worst case, as the hash map may store all elements of nums if no pair is found early. In the best case, the space complexity is O(1).