The Two Sum problem is a common algorithmic problem where you are given an array of integers and a target integer. Your task is to find two numbers in the array that add up to the target and return their indices.

Program Structure

• Includes: The program includes the unordered_map library, which allows for efficient key-value pair storage and retrieval.
• Main Function: This is where the program execution begins.
• twoSum Function: This function takes a vector of integers and a target integer as parameters. It returns a vector containing the indices of the two numbers that add up to the target.

C++ Code

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

/**
 * @brief Finds two indices of numbers in the vector that add up to the target.
 * 
 * @param nums A vector of integers.
 * @param target The target integer.
 * @return A vector of two integers representing the indices of the two numbers.
 */
vector twoSum(const vector& nums, int target) {
    unordered_map<int, int> numMap; // To store number and its index

    for (int i = 0; i < nums.size(); ++i) {
        int complement = target - nums[i]; // The number needed to reach the target

        // Check if complement exists in the map
        if (numMap.find(complement) != numMap.end()) {
            return {numMap[complement], i}; // Return the indices
        }

        // Store the number and its index in the map
        numMap[nums[i]] = i;
    }

    // Return an empty vector if no solution is found
    return {};
}

int main() {
    vector nums = {2, 7, 11, 15};
    int target = 9;

    vector result = twoSum(nums, target);

    if (!result.empty()) {
        cout << "Indices: " << result[0] << ", " << result[1] << endl;
    } else {
        cout << "No two sum solution found." << endl;
    }

    return 0;
}
    

Explanation

The twoSum function operates as follows:

1. It initializes an unordered map numMap to store each number in the array along with its index.
2. It iterates through the array nums, calculating the complement of the current number with respect to the target.
3. If the complement exists in the map, it means we have found the two numbers that sum up to the target. The function then returns their indices.
4. If the complement is not found, the current number and its index are added to the map for future reference.

This approach has a time complexity of O(n), where n is the number of elements in the input array, because each element is processed at most twice.