前言声明

此篇文章的学习内容来自博主whitsats的算法基础课程。

Hash-两数之和

题目

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

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。

示例:

1
2
3
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

接替思路

第一种方式:暴力破解

这种方式很简单,挨个遍历寻找合适的即可。这种方式的时间复杂度为O(n2)O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 表来使用,记录原数组值和键的对应关系,然后与外层循环的差值做比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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数组的结果索引是否为空,如果不为空,那么值即为索引。