JavaScript下的算法基础
前言声明
Hash-两数之和
题目
给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]接替思路
第一种方式：暴力破解
这种方式很简单，挨个遍历寻找合适的即可。这种方式的时间复杂度为O(n2)O(n^2)O(n2)。
function twoSum(arr, tar) {
for (var i = 0; i < arr.length; i++) {
for (var j = 0; j < arr.length; j++) {
if (arr[i] + arr[j] === tar) {
return [arr[i], arr[j]];
}
}
}
}
var arr = [2, 7, 11, 15],
tar = 9;
console.log(twoSum(arr, tar)); // [ 2, 7 ]第二种方式：利用反转键值-数组减少查询时间
将新数组作为 Hash 表来使用，记录原数组值和键的对应关系，然后与外层循环的差值做比较。
var twoSum = function (nums, target) {
var arr = [];
for (var i = 0; i < nums.length; i++) {
var temp = target - nums[i];
// 新数组中有无记录原数组的值恰好等于差值，如果有，则根据这个值，取出在原数组中的键
if (arr[temp] != undefined) {
return [arr[temp], i];
}
// 如果没有，则将索引和值反转并记录
arr[nums[i]] = i;
}
};
var arr = [2, 6, 7, 8, 9, 10, 11, 15],
tar = 17;
console.log(twoSum(arr, tar)); // [ 0, 3 ]这种方式较为巧妙，大体运行方式：
- 第一遍循环 将arr数组索引2位置记录为0。其代表当结果为2时，所对应的索引为0。
- 第二遍循环 将arr数组索引6位置记录为1。其代表当结果为6时，所对应的索引为1。
- 循环完成
每次进入循环都会进行判断：arr数组的结果索引是否为空，如果不为空，那么值即为索引。
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-06-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录