1.字典

1.字典

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

// 增 m.set(‘a’, ‘aa’); m.set(‘b’, ‘bb’);

// 删 m.delete(‘b’); // m.clear();

// 改 m.set(‘a’, ‘aaa’);

<a name="glJkG"></a>
# 题目
<a name="4vC6v"></a>
## 1.两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。
示例 1：<br />输入：nums1 = [1,2,2,1], nums2 = [2,2]<br />输出：[2]
示例 2：<br />输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]<br />输出：[9,4]
说明：
- 输出结果中的每个元素一定是唯一的。
- 我们可以不考虑输出结果的顺序。
思路：
- 求num1和num2都有的值
- 用字典建立一个映射关系，记录nums1里有的值
- 遍历nums2，找出nums1里也有的值
- 新建一个字典，遍历nums1，填充字典
- 遍历nums2，遇到字典里的值就选出来，并从字典中删除
```javascript
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    const map = new Map()
    // 把num1映射为字典，去重
    nums1.forEach(n => {
        map.set(n, true)
    })
    const res = []
    nums2.forEach(m => {
          // 如果nums2中有这个值就提取出来，并删掉map中的值
          // 防止nums2中还有相同的元素，提取重复
        if(map.get(m)) {
            res.push(m)
            map.delete(m)
        }
    })
    return res
};

2.有效的括号（优化）

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “()[]{}”
输出：true
示例 3：

输入：s = “(]”
输出：false
示例 4：

输入：s = “([)]”
输出：false
示例 5：

输入：s = “{[]}”
输出：true

提示：

1<= s.length <= 104
s仅由括号 ‘()[]{}’ 组成 ```javascript /**
- @param {string} s
- @return {boolean} */ var isValid = function(s) {

const map = new Map() map.set(‘(‘, ‘)’) map.set(‘[‘, ‘]’) map.set(‘{‘, ‘}’)

// 定义栈 let stack = [] // 判断字符串的长度，小于2，返回false if(s.length < 2) return false // 得到每一个括号

for(let i= 0; i< s.length;i++) { let c = s[i] // 判断左右括号的类型 // let type = ch(c)

// 左括号入栈，右括号出栈
if(map.has(c)) {
    stack.push(c)
} else {
    // 特殊情况处理，第一个出现的右括号必须和相邻的左边括号是相反的一样的括号
    if(map.get(stack[stack.length -1]) !== c) {
        return false 
    }
    stack.pop()
}

} if(stack.length !== 0) return false

return true };

<a name="Ujtpa"></a>
## 3.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。<br />你可以按任意顺序返回答案。

示例 1：<br />输入：nums = [2,7,11,15], target = 9<br />输出：[0,1]<br />解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：<br />输入：nums = [3,2,4], target = 6<br />输出：[1,2]

示例 3：<br />输入：nums = [3,3], target = 6<br />输出：[0,1]

提示：

- 2 <= nums.length <= 103
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 只会存在一个有效答案

思路：

- 新建一个字典作为婚姻介绍所
- nums里的值，逐个来介绍所找对象，没有合适的就登记着，有了就牵手成功
```javascript
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
      // 新建字典
    let map = new Map()
    for(let i=0;i<nums.length;i++) {
          // 逐个获取信息
        const n = 获取需要寻找的信息
        const n2 = target - n
        // 如果字典中有就直接返回
        if(map.has(n2)) {
            return [map.get(n2), i]
        } else {
              // 没有就先登记
            map.set(n, i)
        }
    }

};

4.无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3

示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，”pwke” 是一个子序列，不是子串。

示例 4:
输入: s = “”
输出: 0

提示：

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

思路：

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

解题：

用双指针维护一个滑动窗口（记录起始和结束为止的下标），用来剪切子串
不断移动右指针，遇到重复字符，就把左指针移动到重复字符的下一位

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

var lengthOfLongestSubstring = function (s) {
  let l = 0; // 定义左指针
  let res = 0; // 结果
  let map = new Map(); // 存放字符和对应下标
  for (let r = 0; r < s.length; r++) {
      // 如果出现了重复字符，则把左指针移到重复字符的下一位。注意同时满足重复字符的索引大于左指针。
      if (map.has(s[r]) && map.get(s[r]) >= l) {
          l = map.get(s[r]) + 1;
      }
      res = Math.max(res, r - l + 1); // 计算结果
      map.set(s[r], r); // 存下每个字符的下标
  }
  return res;
};

5.最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”

示例 2：
输入：s = “a”, t = “a”
输出：”a”

提示：

1 <= s.length, t.length <= 105
s 和 t 由英文字母组成

思路：

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

解题：

用双指针维护滑动窗口

移动右指针，找到包含T的子串，移动左指针，尽量减少包含T的子串的长度

/**
* @param {string} s
* @param {string} t
* @return {string}
*/
var minWindow = function(s, t) {
     // 左右指针
  let l = 0
  let r = 0
  // 定义需要的元素
  const need = new Map()
  for(let c of t) {
        // 设置需要的元素，key为数组中的值， value为需要的数量
      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]
      // 如果需要的元素map中有值
      if(need.has(c)) {
            // 则将需要的元素的个数减一
          need.set(c, need.get(c) - 1)
            // 同时将需要的元素长度减一
          if(need.get(c) === 0) needType -= 1
      }
        // 循环条件 - 需要的长度不为0
      while(needType === 0) {
            // 获取每次循环拿到的符合条件的子串
          const newRes = s.substring(l, r+1)
          // 将最长的子串赋值给res
          if(!res || newRes.length < res.length) res = newRes
            // 定义一个c2用来表示左指针的值
          const c2 = s[l]
          // 如果需要的元素中有左指针指向的值
          if(need.has(c2)) {
                // 就给需要的单个元素的个数加1
              need.set(c2, need.get(c2) + 1)
                // 同时需要的所有元素的个数加1
              if(need.get(c2) === 1) needType += 1
          }
            // 移动左指针
          l += 1
      }
        // 移动右指针
      r += 1
  }
    // 返回结果
  return res
};