嵌套遍历同一个数组的时候，试试Map优化

最近在看数据结构和算法，努力总结出道~

TL:DR

• 嵌套遍历同一个数组的时候，试试Map优化。

因为嵌套遍历的时间复杂度是O(n^2)，有点大，于是可以想下，用空间换时间，在遍历的时候，记录已经遍历过的元素和对应的下标，常用的记录方式就是Map。

• 几乎所有的求和问题，都可以转化为求差问题，这样会变得更简单。

练习：两数求和

没有算法基础的话，第一想法是嵌套遍历。

• 枚举所有不同下标的组合
• 看下和是不是target

var twoSum = function (nums, target) {
  const len = nums.length;
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
};

显然空间O(1)，时间O(n^2)

想想原则，然后优化！

嵌套遍历想到Map，用空间换时间，求和转为求差。

• 在遍历数组的过程中，用 Map 来记录已经遍历过的数字及其对应的索引值。
• 每遍历到一个新数字的时候，看下 target 与该数的差值是否在map里
• 在则直接返回答案，反之继续存储往后走

const twoSum = function (nums, target) {
  // 用对象来模拟 map，存储遍历过的元素和索引
  const map = {};
  const len = nums.length;
  // 遍历数组
  for (let i = 0; i < len; i++) {
    const cur = nums[i];
    const diff = target - cur;
    // 看看差值 在不在 map里
    if (diff in map) {
      // 在就返回答案
      return [map[diff], i];
    }
    // 不在就存储，继续遍历
    map[cur] = i;
  }
};

这样空间就是O(n)，时间也是O(n)~~

可以看下官方视频

引用

• 修言的前端算法和数据结构