Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Brainstorm

Approach #1: Hash Table

  vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> hash;
    vector<int> result;
    for (int i = 0; i < nums.size(); i++) {
        int num1 = nums[i];
        // If the complement of the current number is found in the hash, 
        if (hash.find(target - nums[i]) != hash.end()) {
            result.push_back(hash[target - nums[i]]);
            result.push_back(i);
            return result;
        }
        hash[nums[i]] = i;
    }
    result.push_back(-1);
    result.push_back(-1);
    return result;
  }

Time complexity: $O(n)$

We find the solution in one pass.

Space complexity: $O(n)$

Must maintain a hash table to keep track of results