JavaScript: The Two Sum Problem
From LeetCode’s Top Interview Questions List
This week’s algorithm; Two Sum, is picked from LeetCode’s Top Interview Questions list:
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Check this example out to better understand what the problem is asking:
Example:Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].
Array type of questions like this problem is frequently asked in technical interviews and it has many different ways to solve it. The simple brute force solution is to scan each index pair and their sum of a given array with nested loops. This inefficient solution requires a time complexity of O(n²) with two nested for loops since we first loop through each element of the array and then loop through each element again to return their indices if they add up to the target number.
In this post, I will share another commonly used method to solve this problem. My approach uses a hash and takes linear time; O(n).
