字典

什么是字典

与集合类似，字典也是一种存储唯一值的数据结构，但是它以键值对形式存储。Es6中有Map类型数据结构

const m = new Map()
//增,改
m.set('a', 'aa')
//删
m.delete('a')
m.clear()

leetcode 349

解题思路

• 字典建立映射关系，记录nums1里有的值
• 遍历nums2，找出nums1里也有的值

  代码

  /**
  * @param {number[]} nums1
  * @param {number[]} nums2
  * @return {number[]}
  * 时间复杂度O(m + n)
  * 空间复杂度O(n)
  */
  var intersection = function(nums1, nums2) {
  const map = new Map()
  nums1.forEach(item=>{
   map.set(item, true)
  })
  const res = []
  nums2.forEach(item=>{
   if(map.get(item)){
     res.push(item)
     map.delete(item)
   }
  })
  };

leetcode 20

解题思路

• 空间复杂度 O(n)

• 时间复杂度 O(n)

  代码

  var isValid = function(s) {
  const stack = [];
  const map = new Map()
  map.set('{', '}')
  map.set('[', ']')
  map.set('(', ')')
  for(let i = 0 ; i < s.length; i++) {
     const c = s[i]
     if(map.has(c)) {
         stack.push(c)
     } else {
         const t = stack[stack.length - 1];
         if(
            map.get(t) === c
         ) {
             stack.pop()
         } else {
             return false
         }
     }
  }
  return stack.length === 0
  };

  leetcode 1

  解题思路

• 把nums想象成相亲者

• target想象成匹配条件
• 集合存储相亲双方的下标和值
• 时间复杂度O(n)

• 空间复杂度O(n)

  代码

  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 ]
     }
     map.set(nums[i], i)
  }
  };

  leetcode 3

  无重复字符的最长子串

  解题思路

• 先找出所有无重复的子串

  • 用双指针维护一个滑动窗口，用来剪切子串
  • 不断移动右指针，遇到重复字符，就把左指针右移到重复字符下一位
  • 过程中记录所有窗口长度
• 找出长度最大的子串
• 时间复杂度O(n)

• 空间复杂度O(m)

  代码

  var lengthOfLongestSubstring = function(s) {
  let start = 0
  let maxLength = 0
  const map = new Map()
  for(let end = 0; end < s.length; end ++){
     //拿到的左标，必须在滑动窗口内
     if(map.has(s[end]) && map.get(s[end]) >= start) {
         start = map.get(s[end]) + 1
     }
     maxLength = Math.max(maxLength, end - start + 1)
     map.set(s[end], end)
  }
  return maxLength
  };

leetcode 76

最小覆盖子串

• 先找出所有覆盖子串
  • 用双指针维护一个滑动窗口，用来剪切子串
  • 不断移动右指针，找到包含T的子串，然后左指针右移，尽量减少包含T的子串长度
  • 过程中记录所有窗口长度
• 找出符合要求的子串
• 时间复杂度O(n + m)
• 空间复杂度O(m)

  代码

  /**
  * @param {string} s
  * @param {string} t
  * @return {string}
  */
  var minWindow = function(s, t) {
  let start = 0
  let end = 0
  const map = new Map()
  // map 存储共有多少个不重复的字符
  // A: 1.  B: 1.  C:1
  for(let i = 0; i< t.length; i++) {
     map.set(t[i], map.get(t[i]) ? map.get(t[i]) + 1 : 1)
  }
  let res = ''
  let needType = map.size
  for(let i = 0; i< s.length; i++) {
     const c = s[i]
     if(map.has(c)) {
         map.set(c, map.get(c) - 1)
         if(map.get(c) ===0) {
             needType -= 1
         }
     }
     while(needType === 0){
         const sub = s.substring(start, end +1)
         if(!res || sub.length < res.length) {
             res = sub
         }
         const c2 = s[start]
         if(map.has(c2)) {
             map.set(c2, map.get(c2) + 1)
             if(map.get(c2) === 1) {
                 needType +=1
             }
         }
         start ++;
     }
     end ++;
  }
  return res
  };