专栏首页小康的自留地JavaScript下的算法基础

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数组的结果索引是否为空,如果不为空,那么值即为索引。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 07JavaScript引用类型

    Date提供now()方法,可以得到一个从 1970 年1月1日 00:00:00 至当前系统时间的毫秒数值。

    Dreamy.TZK
  • 计算机网络原理 - 第二章

    应用层协议定义了应用进程间交换的报文类型、报文构成部分具体含义以及交换时序等内容,即语法、 语义和时序等协议三要素内容。

    Dreamy.TZK
  • git的基本使用

    分布式版本控制系统的安全性要高很多,因为每个开发人员电脑里都有完整的版本库,某一个开发人员的电脑坏掉了不要紧,随便从其他开发人员那里复制一个就可以了。而集中式...

    Dreamy.TZK
  • 前端面试题解密:经典算法之冒泡算法(ES6版)及优化

    随着前端的飞速发展,前端业务开发给前端工程师提出了更高的要求,因而算法题也越来越高频次的出现在前端面试中。有很多的小伙伴找胡哥苦诉,在前端实际开发中(除了涉及游...

    胡哥有话说
  • 动态规划(二):0-1背包

    代码中存在两层循环,以二维数组的形式记录中间数据,分别记录不同物品个数在各个空间大小下的最大价值。循环内部存在两种判断,分别用于判断空间大小

    zhipingChen
  • 浙大版《C语言程序设计(第3版)》题目集 习题9-5 通讯录排序

    输入n个朋友的信息,包括姓名、生日、电话号码,本题要求编写程序,按照年龄从大到小的顺序依次输出通讯录。题目保证所有人的生日均不相同。

    C you again 的博客
  • PHP四种排序算法(插入排序)

    阿沐
  • 多图养眼!Partition,荷兰国旗问题与随机快排

    Partition的过程:给定一个数组arr,和一个整数num。把小于等于num的数放在数组的左边,大于num的数放在数组的右边。

    行百里er
  • [数据结构与算法] 排序算法之选择排序和堆排序

    选择排序(select sorting)也是一种简单的排序方法。它的基本思想是: 第一次从arr[0]~arr[n-1]中选取最小值,与arr[0]交换, ...

    时间静止不是简史
  • LeetCode刷题DAY 29:转变数组后最接近目标值的数组和

    给定一个整数数组 arr 和一个目标值 target ,返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近 ...

    三猫

扫码关注云+社区

领取腾讯云代金券