「算法」twoSum问题

一、算法描述

给定一个整数数组，返回两个元素相加等于指定值的元素的索引

例如：nums = [2, 7, 11, 15], target = 9，则返回[0, 1]，因为nums[0] + nums[1] = 9

二、算法实现

1. 暴力算法

思路是：数组元素每2个相加，看看是否与target相等，相等就返回

执行次数与问题规模的函数： T(n) = n * n / 2 - n / 2

复杂度为：O(n * n)

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

2. 使用hash表，空间换时间

复杂度为：O(n)

var towSum = function (nums, target){
  var map = new Map()
  var i = 0
  var n = nums.length
  var diff
  var num
  for(; i < n; i++){
    diff = target - nums[i]
    if(map.has(diff)){
       return [map.get(diff), i]
    }
    map.set(nums[i], i)
  }
  return []
}