Two Sum

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[0] + nums[1] = 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.