字典

• 与集合类似，字典也是一种存储唯一值的数据结构，但它是以键值对的形式来存储。
• ES6中有字典，名为Map。
• 字典的常用操作：键值对的增删改查。 ```javascript const m = new Map();

//增 m.set(“a”, “aaa”) m.set(“b”, “bb”)

// 删 m.delete(“b”) m.clear()

// 改 m.set(“a”, “aa”)

//查 m.get(“a”)

<a name="qTOxg"></a>
## 349 两个数组的交集
输入： nums1 = [1,2,2,1]; nums2=[2,2]<br />输出： [2]<br />解题思路：
- 求nums1和nums2都有的值
- 用字典建立一个映射关系，记录nums1里有的值。
- 遍历nums2,找出nums1里也有的值
解题步骤：
- 新建一个字典，遍历nums1，填充字典。
- 遍历nums2，遇到字典里的值就选出，并从字典中删除。
```javascript
var intersection = function(nums1, nums2) {
    const map = new Map();
    nums1.forEach(n=>{
        map.set(n,true)
    })
    const res = [];
    nums2.forEach(n=>{
        if(map.get(n)) {
            res.push(n);
            map.delete(n)
        }
    })
    return res;
}

时间复杂度：O(m+n);
空间复杂度：O(m);

1 两数之和

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

解题思路：

• 把nums想象成相亲者
• 把target想象成匹配条件
• 用字典建立一个婚姻介绍所，存储相亲者的数字和下标

解题步骤：

• 新建一个字典作为婚姻介绍所。
• nums里的值，依次来介绍所找对象，没有合适的就先登记着，有合适的就牵手成功。

  var twoSum = function(nums, target) {
    const map = new Map();
    for( let i = 0 ; i<nums.length; i++){
        const res = target - nums[i];
        if(map.has(res)) {
            return [map.get(res),i];
        }else{
            map.set(nums[i],i);
        }
    }
  };
  

3 无重复字符的最长子串

输入：abcabcbb
输出：3
解题思路：

• 先找出所有的不包含重复字符的子串。
• 找出长度最大那个子串，返回其长度即可。

解题步骤：

• 用双指针维护一个滑动窗口，用来剪切子串。（双指针其实就是两个变量，用来记录子串的起始位置，）
• 不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位。

• 过程中，记录所有窗口的长度，并返回最大值。

  var lengthOfLongestSubstring = function(s) {
      //左指针下标值
    let left = 0;
    let res = 0;
    const map = new Map();
  
    for(let r = 0; r < s.length; r++) {
       //r右指针移动
          //如果字典中存在重复的值，并且当前所在位置要大于等于左指针的位置，
        if(map.has(s[r]) && map.get(s[r])>=left) {
           //那么此时左指针需要移动到当前重复字符的下一位
            left = map.get(s[r]) + 1;
        }
          //记录滑动窗口最大长度
         res = Math.max(res, r - left + 1);
          //存取数据到字典
         map.set(s[r], r);
    }
  //返回最大的滑动窗口长度
    return res;
  };
  

76 最小覆盖子串

输入：s = “ADOBECODEBANC”, T=”ABC”
输出： “BANC”

解题思路：

• 先找出所有的包含T的子串
• 找出长度最小那个子串，返回即可。

解题步骤：

• 用双指针维护一个滑动窗口
• 移动右指针，找到包含T的子串，移动左指针，尽量减少包含T的子串的长度。

• 循环上述过程，找出包含T的最小子串。

  var minWindow = function(s, t) {
    let left = 0;
    let r = 0;
    const need = new Map();
  
   for(let c of t) {
       need.set(c, need.has(c) ? need.get(c)+1 : 1)
   } 
  
   let needType = need.size;
   let res = "";
    while(r<s.length) {
        const c = s[r];
        if(need.has(c)) {
            need.set(c, need.get(c) - 1);
  
            if(need.get(c) === 0) needType -=1;  
        }
  
        while(needType === 0) {
            const c2 = s[left];
            const newRes = s.substring(left, r+1);
            if(!res || newRes.length < res.length) res= newRes;
  
            if(need.has(c2)) {
                need.set(c2, need.get(c2)+1)
                if(need.get(c2)===1) needType +=1;
            }
  
            left+=1;
        }
        r += 1;
    }
  
    return res;
  };