Two Sum

Table of contents
  1. Problem
  2. With a hash map
  3. With sorting

Problem

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

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

With a hash map

  1. Create a hash map that maps each number in nums to its index.
  2. Go through the elements of num and check if target - num[i] is in the map.
  3. If you found a match, return the indices i and hashmap[target - num[i]].

This approach is $O(n)$.

With sorting

  1. Sort the array in ascending order.
  2. Initialize two pointers i and j at the beginning and the end of the array, respectively.
  3. If nums[i] + nums[j] > target, decrement j.
  4. If nums[i] + nums[j] < target, increment i.
  5. If nums[i] + nums[j] == target, return i and j.

The caveat is i and j are not the indices of the original array. You need to find the indices of nums[i] and nums[j] in the original array.

This approach is $O(n \log n)$ because of the sorting.