JavaScript下的算法基础

前言声明

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

Hash-两数之和

题目

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

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

示例:

1
2
3

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

接替思路

第一种方式：暴力破解

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

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 ]