1. map 和 set 优化算法

在学习算法之前并不是特别了解，map 和 set 的用处。只是感觉多了两个累赘要学习。然而，学习的深入，看到了 java 也有相同的结构，并使用 map 和 set 实际上去优化算法，这才明白两者的不可或缺。下面尽可能的梳理题目，以达到思维固化，快速响应题目的目的。

1）map 做缓存，一次遍历过程中做记忆化存储

1. 两数之和

map 和 object 做检索 时间复杂度是 o(1)，但是 map 更快
通俗做法：两层 for 循环

  1. var twoSum = function(nums, target) {
  2.     let n = nums.length;
  4.     for (let i = 0; i < n - 1; i++) {
  5.         for (let j = i + 1; j < n; j++) {
  6.             if (nums[i] + nums[j] === target) {
  7.                 return [i, j];
  8.             }
  9.         }
  10.     }
  11. };

但是数组有缺陷时间比较长，优化下呢：
其实就是记忆存储，很常规的套路：
1）每次看，自己距离 target 的差值在 map 找到没有？
2）没找到，就存在 map 上
3）找到了，直接返回结束

  1. var twoSum = function(nums, target) {
  2.     let map = new Map();
  3.     let n = nums.length;
  5.     for (let i = 0; i < n; i++) {
  6.         let key = nums[i];
  8.         let left = target - key; // 看看之前有没有存到过合适的值
  9.         if (map.has(left)) {
  10.             return [map.get(left), i];
  11.         }
  12.         map.set(key, i);
  13.     }
  14. };

2. 双向链表

146. LRU 缓存

题目简述：设计一种LRU数据结构，有一个初始容量。没有超过容量时，可以正常读写。超过容量，就把使用最少的数据删除。
原始思考：结构设计要包含两层意思：1）数据存储本身 2）每个数据的使用新旧程度
对于 1）没有其他要想的，使用一个 map 就可以，对于 2）要用栈、队列可以吗，答案是否定的，因为数组的检索复杂度比较高：
image.png
权衡一下，使用 双向链表，就是这么骚。
一种解释：
image.png

我的实现：https://www.yuque.com/wangtengyun/vwapnv/cy9knd