# Two Sum

Updated Sep 12, 2023#dsa#leetcode#hash-tables

The Two Sum problem is a popular coding interview question that asks you to find two numbers in an array that add up to a given target value. The problem statement typically provides an integer array $nums$ and an integer $target$. You need to find two elements in the nums array such that their sum equals $target$ and return their indices as an array.

For example, given an array $nums = [2, 7, 11, 15]$ and a target value $target = 9$, the function should return $[0, 1]$ because $nums + nums = 2 + 7 = 9$.

The problem can be solved using various algorithms such as brute force, two-pass hash table, or one-pass hash table. The time and space complexity of the algorithm may vary based on the approach used.

Here’s a solution in C++:

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

// Function to find two elements that add up to a target value
vector<int> twoSum(vector<int> &nums, int target) {
// Create an empty hash map
unordered_map<int, int> map;
// Loop through the array
for (int i = 0; i < nums.size(); i++) {
// Calculate the complement of the current element
int complement = target - nums[i];
// Check if the complement is already in the hash map
if (map.count(complement) > 0) {
// If yes, return the indices of both elements
return {map[complement], i};
}
// Otherwise, store the current element and its index in the hash map
map[nums[i]] = i;
}
// If no solution is found, return an empty vector
return {};
}

The time complexity of the above solution to the Two Sum problem is $O(n)$, where $n$ is the length of the input array nums. This is because the algorithm performs a single pass through the array, and for each element in the array, it performs a constant-time dictionary lookup operation to check if the complement of the current element exists in the dictionary.