Two sum practice problem

Two Sum

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to the target.

You may assume that each input has exactly one solution, and you cannot use the same element twice.

The answer may be returned in any order.

Brute Force Solution

A straightforward approach uses nested loops to check every pair of numbers. While simple to implement, this method has a time complexity of $O(n^2)$, which becomes inefficient for large arrays.

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> twoSum(vector<int>& nums, int target){
    for(int i = 0; i < nums.size(); i++){
        for(int j = i+1; j < nums.size(); j++){
            int sum = nums[i] + nums[j];
            if(sum == target)
                return {i,j};
        }
    }
    return {};
}
 
int main() {
    vector<int> nums = {2,7,15,46};
    int target = 9;
    auto output = twoSum(nums,target);
    for(int out : output)
        cout << out << " ";
}

Optimized Hash Map Solution

Similar to Valid Anagram and Longest Substring Without Repeating Characters, this problem can be solved efficiently using a hash map. By storing each number’s index as we iterate, we can check if the complement (target - current number) exists in the hash map, reducing the time complexity from $O(n^2)$ to $O(n)$ with $O(n)$ space complexity.

For more details on hash map data structures and their time complexity characteristics, see Hash Maps.

#include <unordered_map>
#include <vector>
using namespace std;
 
class Solution {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> hash;
    for (int i = 0; i < nums.size(); i++) {
      if (hash.count(target - nums[i])) {
        return {i, hash[target - nums[i]]};
      }
      hash[nums[i]] = i;
    }
    return {};
  }
};