1 两数之和(Two Sum)

题目

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

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

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

解答

暴力遍历法

const twoSum = function (nums, target) {
  for (let i = 0; i < nums.length-1; i++) {
    for (let j = i+1; j < nums.length; j++) {
      if (j !== i && nums[i] + nums[j] == target) {
          return [i, j]
      }
    }
  }
};

Runtime: 172 ms, faster than 16.41% of JavaScript online submissions for Two Sum.

Memory Usage: 34.7 MB, less than 66.18% of JavaScript online submissions for Two Sum.

哈希表

唠唠数据结构——哈希表 唠叨一下js对象与哈希表那些事

哈希表是一种介于数组和链表之间的数据结构

数组

数组就是一个位置一个坑，需要数据基本整齐的。这样查找很方便，有key就能找到value，用value找key稍微麻烦点。数据的增添和删除上就更麻烦了，删了第一个，整个数组都要一个个往前挪一位。

链表

每个链表元素只记得怎么找到后面那个元素。类似于做广播操的队列，每个人只需要记住前面那个人是谁，队伍就能排起来了。 这样数据的增删就很方便，只需要换一个元素记就行了。但数据的查询就很麻烦，只能从头往后一个个查，直到找到。

哈希表

哈希表就是粘在一个个数组位置上的链表。

通过哈希函数，把key换算成数组的位置，然后放入数组。如果有冲突，就用链表结构，粘在这个数组位置后面。

要找的时候，通过哈希函数算出元素所在数组的位置，以此进入链表，再一个个摸到想要的元素。这比从头一个个摸过来要快得多。 要删改的时候，也是算出数组位置进入，直接修改前后两个链表的指向即可。这比数组一个个挪位置也要快得多。

换言之，哈希表是在用空间换时间。

image-20190625143722882

那么哈希函数是怎么计算出数组的位置的呢？ 最简单的方式可以使用取模的方式来确定下标。数组长度多大，就取多大数的模（最好是素数）

const twoSum = function (nums, target) {
  if (Object.prototype.toString.call(nums) !== '[object Array]' || typeof target !== 'number') {
    // 排除掉奇怪的情况，能节约测试的时间
    alert("input type incorrect");
    return;
  }

  const arrMap = new Map()
  for (let i = 0; i < nums.length; i++) {
    arrMap.set(nums[i], i)
  }
  /*
  建立哈希表
  arrMap = { 2 => 0, 7 => 1, 11 => 2, 15 => 3 }
  值为key，下标为value
  */

  for (let i = 0; i < nums.length; i++) {
    const result = target - nums[i];
    if (arrMap.has(result) && arrMap.get(result) !== i) {
      // 有相减之后的值，且不是自己（不能复用元素）
      return [arrMap.get(result), i];
    }
  }
};

Runtime: 56 ms, faster than 92.05% of JavaScript online submissions for Two Sum. Memory Usage: 36.1 MB, less than 13.21% of JavaScript online submissions for Two Sum.

这里有个有趣的思路。题目中是两数相加等于targetnums[i] + nums[j] == target，而这里是算出距离target还差多少，然后找那个差距的值const result = target - nums[i]; arrMap.has(result)

一遍哈希表：

const twoSum = function (nums, target) {
  if (Object.prototype.toString.call(nums) !== '[object Array]' || typeof target !== 'number') {
    alert("input type incorrect");
    return;
  }

  const arrMap = new Map()
  for (let i = 0; i < nums.length; i++) {
    const result = target - nums[i];
    if (arrMap.has(result)) {
      return [arrMap.get(result), i]
    }
    arrMap.set(nums[i], i)
  }
};

Runtime: 52 ms, faster than 96.57% of JavaScript online submissions for Two Sum.

Memory Usage: 35.1 MB, less than 33.80% of JavaScript online submissions for Two Sum.

感觉哈希表和对象很像，那如果用对象改写呢？

const twoSum = function (nums, target) {
  if (Object.prototype.toString.call(nums) !== '[object Array]' || typeof target !== 'number') {
    return;
  }

  const arrobj = {}
  for (let i = 0; i < nums.length; i++) {
    arrobj[nums[i]] = i
  }

  for (let i = 0; i < nums.length; i++) {
    const result = (target - nums[i]).toString();
    // arrobj的key是string，因此必须转换一下才能用

    if (arrobj.hasOwnProperty(result) && arrobj[result] !== i) {
      return [arrobj[result], i];
    }
  }
};

Runtime: 72 ms, faster than 61.90% of JavaScript online submissions for Two Sum.

Memory Usage: 36.3 MB, less than 10.22% of JavaScript online submissions for Two Sum.

感觉和map差不多，稍逊一筹。

那么Map和Object的区别是啥呢？

ES5对象与ES6 Maps的异同

ECMAScript 6 入门

1. Object对象有原型，原型链上的键名有可能和你自己在对象上的设置的键名产生冲突。

   除非我们使用Object.create(null)创建一个没有原型的对象；

2. 在Object对象中， 只能把String和Symbol作为key值

   但是在Map中，key值可以是任何基本类型(String, Number, Boolean, undefined, NaN….)，或者对象(Map, Set, Object, Function , Symbol , null….);

   Object 结构提供了“字符串—值”的对应，Map 结构提供了“值—值”的对应，是一种更完善的 Hash 结构实现。如果你需要“键值对”的数据结构，Map 比 Object 更合适。 【比如map的key是一个引用，那么它的操作，是直接把引用内容复制到新的地方，而obj则是转成string之后再贴到新的地方】

3. Map中不能有重复的key

4. 通过Map中的size属性， 可以很方便地获取到Map长度， 要获取Object的长度， 没有直接的方法；

原型链

lint的规范是不让用obj.hasOwnProperty的。

在大型系统中，如果要实例化一个object，一般是用Object.creat(null)，这样object就不会继承任何的方法。我们在prototype写方法的时候也不会污染原有的Object原型。毕竟object是所有人的爹，这样做会更加安全吧