1. Two Sum

Difficult: Easy

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.

 

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2:

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

Input: nums = [3,3], target = 6
Output: [0,1]
 

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.
 

Approach:

Simply using a brute force technique create two loops , loop over each element i for each element i iterate through the rest of the array with index j, starting from i+1.

Check if the sum of nums[i] + nums[j] === target

If it does then return the indices [i,j]

Javascript Solution (brute force):

var twoSum = function(nums, target) {
    for(let i = 0 ; i < nums.length; i++) {
        for(let j = i+1; j < nums.length; j++){
            if(nums[i] + nums[j] == target) return [i,j]
        }
    }
};


Time Complexity O(n^2), Space complexity O(1)

Approach 2:

Another efficient way to solve this problem is by using a hash map/table. Which significantly reduces the time complexity from O(n^2) to O(n).

Javascript Solution 2 (Hash Map):

var twoSum = function(nums, target) {
    let map = new Map()  // initialize map
    for(let i = 0 ; i < nums.length; i++){ // loop through all elements once
        let complement = target - nums[i] // calculate complement
        if(map.has(complement)){ // check if map contains the complement
            return [map.get(complement), i] //answer
            
        } else{
           map.set(nums[i], i) // sets value in map if solution not found to fetch later if solution is found
}
    }
};