题目描述
给定一个整数数组 和一个目标值 ，在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
例如:
nums = [2, 7, 11, 15]
target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
分析
最容易想到是暴力解法， 即使用两个循环， 遍历所有可能的情况， 查找两两相加结果是期望值的结果
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
// 暴力解法
// 时间复杂度：O(n的二次方)
// 空间复杂度：O(1)
var twoSum = function(nums, target) {
let l = nums.length
for (let i = 0; i < l;i++) {
for (let j = i + 1; j < l; j++) {
// 如果两数相加等于期望值 返回两数的下标
if (nums[i] + nums[j] === target) {
return [i, j]
}
}
}
};
这种方式好比两个人对暗号， 每两个人都要互相询问一遍，才能配对，时间消耗大。
为了减少时间复杂度， 可以使用登记册(Hash表)的方式，这是一种用更多的空间 ,换取更快的时间的一种常用法，步骤为先循环一遍，让每个人把自己的暗号和对应索引记录在登记册上。所有人登记完毕后， 再次遍历一遍，从记录完成的Hash表中找到每个人需要对应的暗号，如果找到了，就返回自己的索引和Hash表中对上暗号的索引。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
// 两遍Hash表
// 时间复杂度：O(n) (2 * n)
// 空间复杂度：O(n) 所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素
var twoSum = function(nums, target) {
let hash = {}
// 把数组中每个元素的值和数组索引， 作为key和value, 记录在hash表中
for (let i=0; i < nums.length; i++) {
hash[nums[i]] = i
}
// 从hash表中取配对结果
for (let i=0; i < nums.length; i++) {
// t为当前数组元素满足相加和为target的元素值
let t = target - nums[i]
// 如果hash表中有配对值 又不是当前元素自己， 则配对成功
if (hash[t] >= 0 && hash[t] !== i) {
return [i, hash[t]]
}
}
};
hash表登记和配对的过程可以同时进行，如果一个人在Hash表中找到了自己的暗号，则配对成功， 返回Hash表中对应暗号的下标和自己的下标，否则就把自己的暗号登记下来，这样一遍下来就可以对上暗号
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
// 一遍 Hash表
// 时间复杂度：O(n)
// 空间复杂度：O(n)
var twoSum = function(nums, target) {
let hash = {}
for (let i=0; i < nums.length; i++) {
let t = target - nums[i]
// hash表中有值 则配对成功返回
if (hash[t] >= 0) {
return [hash[t], i]
}
// 没找到值， 把自己的值和下标登记在hash表
hash[nums[i]] = i
}
};
You have been upvoted by all four members of the @steemexplorers team. Steemexplorers is an initiative to help bring all Steemians information on various services and communities operating all on the STEEM blockchain in a centralized location to save you time and help you grow here on Steemit. It's free, it's easy, and there's a whole lot of information here that you can put to good use. Please come by our discord channel to learn more and feel free to ask as many questions as you'd like. We're here to help! Link to Discord: https://discord.gg/6QrMCFq
Congratulations @hughie8! You have completed the following achievement on the Steem blockchain and have been rewarded with new badge(s) :
You can view your badges on your Steem Board and compare to others on the Steem Ranking
If you no longer want to receive notifications, reply to this comment with the word
STOPTo support your work, I also upvoted your post!
Vote for @Steemitboard as a witness to get one more award and increased upvotes!