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 and an integer . You need to find two elements in the nums array such that their sum equals and return their indices as an array.
For example, given an array and a target value , the function should return because .
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 , where 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.