字典 Map

• 用来存储唯一值的一种数据结构, 通常以 [键, 值] 对 的形式来存储数据
• 特点是一一对应，也称为映射
• Es6 中的 Map，WeakMap
• 常用方法：set, get, remove, has, size, clear, keys, values

常用算法-两数之和

/**
 * @param 需求 给定一个数组 [1,5,9,15] 输出 和为 16 的两个数字对应下边
 */
const sum = function (nums, result) {
  let map = new Map();

  for (let i = 0; i < nums.length; i++) {
    let n = nums[i];
    let diff = result - n;

    if (map.has(diff)) {
      return [map.get(diff), i];
    }
    map.set(n, i);
  }
};

// test
let nums = [4, 9, 11, 17],
  result = 21;
sum(nums, result); // [0,3]

常用算法-无重复字符的最长子串

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  let left = 0;
  let result = 0;
  let map = new Map();

  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i]) && map.get(s[i]) >= left) {
      left = map.get(s[i]) + 1;
    }

    result = Math.max(result, i - left + 1);
    map.set(s[i], i);
  }
  return result;
};
// test 
lengthOfLongestSubstring("abcabcbb") // 3
lengthOfLongestSubstring("pwwkew") // 3

常用算法-有效的括号

在下方