Given two inputs: an integer array nums and an integer value target. Implement a function twoSum such that it returns the indicies of the two elements in nums that sum up to the target.
Input Constraints: Length of nums will be between $2$ and $10^5$.
Output Constraints: There is exactly one pair of elements in nums that sum up to the target.

Naive Approach to Solution

We can iterate over the nums array to select an element. Then a nested loop can pick the second element from the nums array to check if the sum of both elements is target.

func twoSum(nums, target):
  for index1 in range(0, length(nums)):
      for index2 in range(index1+1, length(nums)):
          if nums[index1]+nums[index2]==target:
              return [index1, index2]

We know from the problem statement that there is always a pair of elements in nums that sum up to the target. So the condition nums[index1]+nums[index2]==target will eventually evaluate to true.
Time Complexity in the worst case scenario: $O(n^2)$, because we are using nested loops to select two values from nums array.
Space Complexity in the worst case scenario: $O(1)$, because we are not using additional memory while executing this solution.

Optimized Approach to Solution

Instead of using nested loops to select two values, we can maintain a hashmap of the elements we encountered during the iteration.
For each value that we encounter during the iteration, we can store the key-value pair of (nums[index], index) in the hashmap. Assuming we found the first value of solution (x) then its difference from target(target-x) should be present in the hashmap.

func twoSum(nums, target):
  hm = HashMap()
  for index in range(0, length(nums)):
      diff = target - nums[index]
      if diff in hm:
          return [index, nums[index]]
      else:
          hm[nums[index]] = index

Time Complexity in the worst case scenario: $O(n)$, because we have to perform only a single iteration over the nums array.
Space Complexity in the worst case scenario: $O(n)$, because for certain inputs we might have to store almost all elements of nums inside the hashmap.

Walkthrough of Optimized Approach

Input: nums = [3, 6, 2, 4], target = 6

Initilized Values: hm is a empty hashmap (it will map values from nums to their index)

Solution Code (Go)

func twoSum(nums []int, target int) []int {
  hm := make(map[int]int)
  for index, val := range nums {
      diff := target-val
      _, found := hm[diff]
      if found {
          return []int{index, hm[diff]}
      }
      hm[val] = index
  }
  return []int{0, 1}
}

Pattern recognition

When you have to check for two (or multiple) values in single array or string such that they fulfill a particular condition. Then you can reduce the lookup time from $O(n^2)$ to $O(1)$ by opting to use a hashmap to store the elements/characters of the array/string instead of executing nested loops.

References

• https://leetcode.com/problems/two-sum/description/