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 numsnums and an integer targettarget. You need to find two elements in the nums array such that their sum equals targettarget and return their indices as an array.

For example, given an array nums=[2,7,11,15]nums = [2, 7, 11, 15] and a target value target=9target = 9, the function should return [0,1][0, 1] because nums[0]+nums[1]=2+7=9nums[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)O(n), where nn 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.