嵌套遍历同一个数组的时候，试试Map优化
最近在看数据结构和算法，努力总结出道~
- 嵌套遍历同一个数组的时候，试试Map优化。
因为嵌套遍历的时间复杂度是O(n^2)，有点大，于是可以想下，用空间换时间，在遍历的时候，记录已经遍历过的元素和对应的下标，常用的记录方式就是Map。
Map的好处是，查找的时间复杂度是O(1)，给已经遍历过的元素建立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)~~
可以看下官方视频
