# 1 两数之和(Two Sum)

## 题目

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

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

示例:

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

## 解答

### 暴力遍历法

```javascript
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.

### 哈希表

[唠唠数据结构——哈希表](https://zhuanlan.zhihu.com/p/30344731) [唠叨一下js对象与哈希表那些事](https://segmentfault.com/a/1190000007692754)

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

**数组**

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

**链表**

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

**哈希表**

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

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

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

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

![image-20190625143722882](http://ww2.sinaimg.cn/large/006tNc79ly1g4de7dkffrj308u0andi6.jpg)

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

```javascript
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.

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

一遍哈希表：

```javascript
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.

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

```javascript
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的异同](https://www.zcfy.cc/article/es5-objects-vs-es6-maps-8211-the-differences-and-similarities-appendto-web-development-training-courses-for-teams-795.html)

[ECMAScript 6 入门](http://es6.ruanyifeng.com/)

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的长度， 没有直接的方法；

[原型链](https://notes-12.gitbook.io/notes/js-yuan-xing-lian)

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

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