两数之和
描述:
题解:
思路一:暴力循环法
暴力循环法的思路很简单,也比较符合大家的惯性思维。双层数组遍历,外层循环遍历nums
数组,内层循环判断数组余下的值是否存在相加等于target
的元素
ES6
function twoSum(nums, target) {
let i = 0, j;
for (; i < nums.length; i++) {
for (j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return [i, j];
}
}
}
}
时间复杂度:O(n^2)
思路二:两遍散列表
对于这种问题,在算法中首先想到的是用散列表来实现,把 O(n) 的问题转换成 O(1) 的问题来实现。在这里,我们只是使用散列表的思想,在Javascript里面没有散列表这种数据类型,我们可以使用 Map
来实现。
ES6
function twoSum(nums, target) {
const map = new Map(nums.map((value, key) => [value, key]))
let i = 0, complement;
for (i; i < nums.length; i++) {
complement = target - nums[i];
if (map.has(complement) && map.get(complement) !== i) {
return [i, map.get(complement)]
}
}
}
时间复杂度:O(n)
思路三:一遍散列表
在思路二的基础上做的优化。我们没必要一开始就对整个nums
数组做一遍散列函数转换。在迭代nums
数组的时候,我们把元素插入到Map
的同时,会首先检查Map
中是否已存在满足条件的目标元素。如果存在,直接返回结果;不存在,就插入到Map
里面
ES6
function twoSum(nums, target) {
const map = new Map()
let i = 0, complement
for (i; i < nums.length; i++) {
complement = target - nums[i]
if (map.has(complement)) {
return [map.get(complement), i]
}
map.set(nums[i], i)
}
}