1. 两数之和

分析：获取相加数字后的两个目标数据

题目

const numbers = [2,7,11,15]
const target = 9
const twoSum = (numbers, target) => {
  // ...
}
console.log(twoSum(numbers, target))
// [0, 1] 或 [1, 0]

// 出题者保证
// 1. numbers 中的数字不会重复
// 2. 只会存在一个有效答案

思路:

1. 两根手指法
2. hashMap 法

答案

hashMap 法 (空间换时间)

时间复杂度:n

思路：

1. 声明对象 map
2. 遍历数组，计算差值
   • 不存在则存入 map
   • 存在则返回

const numbers = [2,7,11,15]
const target = 9

// map法
const twoSum = (numbers, target) => {
  const map = new Map()

  for(let i=0;i<numbers.length;i++){
      const number = numbers[i]
      const result = target - number
      if(map.has(result)){
        const resultIndex = map.get(result)
         return [resultIndex,i]
      }else{
        map.set(number, i)
      }
  }

}
console.log(twoSum(numbers, 9))

双 for

时间复杂度:n²

const numbers = [2,7,11,15]
const target = 9

// 双for
const twoSum = (numbers, target) => {

  for(let i=0;i<numbers.length;i++){
      const num1 = numbers[i]
        for(let j=1;j<numbers.length;j++){
            const num2 = numbers[j]
            let result = target - num1
            if(result === num2){
              return [i,j]
            }
        }
  }
}
console.log(twoSum(numbers, 9))

1. 两数之和

分析：获取相加数字后的两个目标数据

答案

对撞指针

function sum(arr,target){
  let left = 0,right = arr.length-1
  while(left<right){
    if(arr[left]+arr[right]>target){
      right--
    }else if(arr[left]+arr[right]<target){
      left++
    }else if(arr[left]+arr[right]==target){
      return [left,right]
    }
  }
}

let arr = [1,2,3,4,5]
let target = 5

console.log(sum(arr,target))