Title

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]

Analyze

题解 1: 暴力法

var twoSum = function(nums, target) {
var length = nums.length
for (var x = 0; x < length; x++) {
for (var y = x + 1; y < length; y++) {
if (nums[x] + nums[y] === target) {
var arr = []
arr.push(x)
arr.push(y)
return arr
}
}
}
}
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(1)

题解 2-1: 哈希表

思路:

需要留意的是, 如果数组中有重复的值比如 [5, 5], target = 10 这种情况的处理

  • 遍历一次数组, 查询当前哈希表中是否有和当前索引值 nums[i] 对应的匹配值 target - nums[i];
    • 若有, 则返回它们两个值的索引;
    • 若没有, 则将当前索引值和下标存入哈希表中;
var twoSum = function(nums, target) {
let numsObj = {}
for (let i = 0; i < nums.length; i++) {
let current = nums[i]
let match = target - current
if (match in numsObj) {
return [i, numsObj[match]]
}
numsObj[current] = i
}
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

题解 2-2: 使用 Map, 思路同哈希表

var twoSum = function(nums, target) {
var map = new Map()
for (let i = 0; i < nums.length; i++) {
const targetValue = target - nums[i]
const getTargetValue = map.get(targetValue)
if (typeof(getTargetValue) === 'number') {
return [i, getTargetValue]
}
map.set(nums[i], i)
}
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(n)

Sister Title

15、16、18