数据结构-字典

字典定义

基本操作

const m = new Map();

// 增
m.set('a', '123');
m.set('b', 'bb');

// 删
m.delete('b');
// m.clear();  // 删除所有

// 改
m.set('a', 'aa');


// 查
console.log(m.get('a'));

刷题

LeetCode: 349.两个数组的交集

题目描述

解题思路

解题步骤

Code

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersection = function(nums1, nums2) {
    const map = new Map();
    nums1.forEach(n => {
        map.set(n, true); // 为nums1中的每个数建立一种映射关系
    });
    const res = [];
    nums2.forEach(n => {
        if(map.get(n)){  // 判断nums2中的数是否在nums1中
            res.push(n);
            map.delete(n);
        }
    })
    return res;
};

时间复杂度 空间复杂度分析

• 因其中有forEach()，所以时间复杂度为O(n)
• 因字典中的值随数组的大小而线性增长，所以空间复杂度为O(n)

LeetCode: 020. 有效的括号(优化)

题目描述

代码优化

Code

/**
 * @param {string} s
 * @return {boolean}
 */

 var isValid = function(s) {
  if(s % 2 === 1) false;
  const stack = [];
  const map = new Map();  // 1. 实例化map
  map.set('(', ')').set('[', ']').set('{', '}');    // 2. 添加键值对
  for (let i = 0; i < s.length; i++){
    const c = s[i];
    if( map.has(c)){   // 3. 改写判断条件 判断键是否在字典中
      stack.push(c);
    }else{
      const t = stack[stack.length - 1];
      if(map.get(t) === c ){    // 4. 判断是否构成完整的键值对
        stack.pop();
      }else {
        return false;
      }
    }
  }
  return stack.length === 0;
};

时间复杂度 空间复杂度分析

• 因其中有for循环，所以时间复杂度为O(n)
• 因其中有数组，所以空间复杂度为O(n)

LeetCode: 001.两数之和

题目描述

解题思路

解题步骤

Code

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

时间复杂度 空间复杂度分析

• 因其中有for循环，所以时间复杂度为O(n)
• 因字典中的值随数组的大小而线性增长，所以空间复杂度为O(n)

LeetCode: 003.无重复字符的最长子串

题目描述

解题思路

解题步骤

Code

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let l = 0;      // 定义左指针
    let res = 0;    // 定义结果
    const 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;
};

时间复杂度 空间复杂度分析

• 因其中有for循环，所以时间复杂度为O(n)
• 因字典中的值随数组的大小而线性增长，所以空间复杂度为O(n)

LeetCode: 076.最小覆盖子串

题目描述（有点难）

解题思路

解题步骤

Code

// 不会做  可参考 刷题视频 7-6 LeetCode：76. 最小覆盖子串.mp4

时间复杂度 空间复杂度分析

• 因其中有for循环，所以时间复杂度为O(n)
• 因字典中的值随数组的大小而线性增长，所以空间复杂度为O(n)

总结