1. Two Sum with new solutions

⛳ Leetcode Overview

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]
 

📃 Analysis

The normal way is to use two for loops to find the two numbers that add up to the target. But with using the javascript inbuilt Object or Map data types, we can reduce the time complexity from O(n^2) to O(n)

提示

Separate the question into 4 parts

• Loop through the array
• Keep track of the difference between each number and the target
• Check if the difference exists in the Object/Map variable
• If it exists, return the index, otherwise, store the index with the current number as the key

✏ Code Editor

1. Option 1: Using two for loops

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

2. Option 2: Using one for loop with an extra object variable

实时编辑器

function twoSumWithObject(nums, target) { let obj={}; for (let i = 0; i < nums.length; i++) { const diff = target - nums[i]; if(obj[diff]!==undefined){ return [obj[diff],i] } else{ obj[nums[i]] = i } } }; const testCases=[{nums:[2,7,11,15],target:9},{nums:[3,2,4],target:6},{nums:[1,8,3,3],target:6}] render( <RunTestCases mainFn= {twoSumWithObject} testCases={testCases} /> )

function twoSumWithObject(nums, target) {
  let obj={};
  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    if(obj[diff]!==undefined){
        return [obj[diff],i]
    } else{
        obj[nums[i]] = i
    }
  }
};

const testCases=[{nums:[2,7,11,15],target:9},{nums:[3,2,4],target:6},{nums:[1,8,3,3],target:6}]

render(
  <RunTestCases
    mainFn= {twoSumWithObject}
    testCases={testCases}
  />
)

结果

Loading...

Option 3: Using one for loop with an extra Map variable

实时编辑器

function twoSumWithMap(nums, target) { let map = new Map(); for (let i = 0; i < nums.length; i++) { const diff = target - nums[i]; if (map.has(diff)) { return [map.get(diff), i]; }else { map.set(nums[i], i); } } } const testCases=[{nums:[2,7,11,15],target:9},{nums:[3,2,4],target:6},{nums:[1,8,3,3],target:6}] render( <RunTestCases mainFn= {twoSumWithMap} testCases={testCases} /> )

function twoSumWithMap(nums, target) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    if (map.has(diff)) {
      return [map.get(diff), i];
    }else {
      map.set(nums[i], i);
    }
  }
}

const testCases=[{nums:[2,7,11,15],target:9},{nums:[3,2,4],target:6},{nums:[1,8,3,3],target:6}]

render(
  <RunTestCases
    mainFn= {twoSumWithMap}
    testCases={testCases}
  />
)

结果

Loading...