Better

什么是 ARTS 打卡，主要分成 4 个部分，分别是 Algorithm、Review、Tip 和 Share，对应起来分别是完成每周至少完成一个 Leetcode 算法题，阅读并点评至少一篇英文技术文章，学习至少一个技术技巧，分享一 篇有观点和思考的技术文章。

背景介绍

关于 Algorithm：每周至少完成一个 Leetcode 算法题，主要是为了编程训练和学习，从易到难逐步进阶，完成之后，可以看下讨论区是否有更好的解法

关于 Review：阅读并点评至少一篇英文技术文章，主要是为了学习英文，如果你英文不行，基本上无缘技术高手

关于 Tip：学习至少一个技术技巧，主要是为了总结和归纳你在日常工作中所遇到的知识点

关于 Share：分享一篇有观点和思考的技术文章，主要是为了建立你的影响力，能够输出价值观

Algorithm

本周是一道比较简单的题目，名为 Two Sum，给定一个数组和目标值，返回数组中相加等于目标值的两项的下标。

本人代码

var twoSum = function(nums, target) {
    for(var i = 0; i < nums.length; i++) {
        var number = nums[i]
        var delta = target - number
        var index = nums.indexOf(delta)
        if( index > -1 && index !== i) {
            return [i, index]
        }
    }
};

分析下来，这个解法有很大的性能空间，主要是 indexOf 内部肯定也是开循环查找，如此时间复杂度便是O(n ^ 2)，解决思路：用 Map 代替 Array，因为 Map 的元素查找复杂度为 O(1)，优化后代码如下

var twoSum = function(nums, target) {
    if(nums.length === 2) {
        return [0, 1]
    }
    const length = nums.length
    let hashTable = Object.create(null)
    for(let i = 0; i < length; i++) {
        hashTable[nums[i]] = i
    }
    for(let i = 0; i < length; i++) {
        var number = nums[i]
        var delta = target - number
        let found = hashTable[delta]
        if(found !== undefined && found !== i) {
            return [i, found]
        }
    }
};

我们首先将 Array 转成 Map 结构，如此在第二次循环中查找指定元素是否存在就无需使用循环，性能自然更好一些。

接下来看一种更优秀的写法，将 Array 转 Map 的过程，放在查找的循环中

var twoSum = function(nums, target) {
    if (nums.length === 2) return [0, 1];
    const len = nums.length;
    let map = {};
    for(let i = 0; i < len; i++) {
        let n = target - nums[i];
        let find = map[n];
        if(find !== undefined) return [find, i];
        else map[nums[i]] = i;
    }
};

这种方案，我一开始想，会不会错过彼此，比如目前 n 元素在 map 中不存在，但是在后续的 nums 中是有的，但仔细一想，前一次错过彼此了，但是循环到后面的指定元素的时候，前一个元素肯定就已经存在于 map 中了，因此这是一种很棒的解法。

Review

本周阅读的文章来自 medium，名为 The Pitfalls of Async/Await in Array Loops。也就是说 Async/Await 在 Array 循环中的陷进。

如果你在 forEach 循环中使用 Async/Await，不会如你预期般运行，演示代码如下

async function getTodos() {
  await urls.forEach(async (url, idx) => { 
    const todo = await fetch(url);
    console.log(`Received Todo ${idx+1}:`, todo);
  });
  console.log('Finished!');
}
getTodos()

打印结果如下

Finished!
Received Todo 2, Response: { ··· }
Received Todo 1, Response: { ··· }
Received Todo 3, Response: { ··· }

从打印结果中，我们可以看出两个问题

• await 并不能使 forEach 等待，所以先打印出了 Finished
• 内部的 fetch 请求并不是一个接着一个执行的

原因我想其实也很好解释

• 第一：await 后面需要的是一个 Promise，很明显 forEach 返回的并不是 Promise，而是 undefined，因此无效
• 第二：forEach 本身并不支持处理传入的回调函数为 async 函数的情况，因此通过回调函数的方式调用了多个 async 函数，和我们调用多个 async 函数是类似的，如何他们要保证有序呢？

第一个问题很好解决，首先 await 需要搭配 Promise，同时我们需要等到多个 fetch 请求执行完毕，很容易想到 Promise.all，代码修改如下

async function getTodos() {
  const promises = urls.map(async (url, idx) =>
    console.log(`Received Todo ${idx+1}:`, await fetch(url))
  );
  await Promise.all(promises);
  console.log('Finished!');
}

这样仅仅是解决了第一个问题，但是内部请求执行并不是 one by one 的。如果严格要求 one by one，该如何解决呢

其实解决办法很简单，既然 forEach 函数不支持，直接按照最原始的逻辑，手写代码即可

async function getTodos() {
  for (const [idx, url] of urls.entries()) {
    const todo = await fetch(url);
    console.log(`Received Todo ${idx+1}:`, todo);
  }
  console.log('Finished!');
}

Tip

如何检测对象中是否存在环引用，我们首先学习下 ES6 中 Map 和 Object 的区别，毕竟在之前，经常把 Object 当做 Map 使用

• 一个 Object 的键只能是字符串或者 Symbols，但一个 Map 的键可以是任意值，包括函数、对象、基本类型。
• Map 中的键值是有序的，而添加到对象中的键则不是。因此，当对它进行遍历时，Map 对象是按插入的顺序返回键值。
• 你可以通过 size 属性直接获取一个 Map 的键值对个数，而 Object 的键值对个数只能手动计算。
• Map 可直接进行迭代，而 Object 的迭代需要先获取它的键数组，然后再进行迭代。

这里利用 Map 结构可以轻松的检测是否有环

var a = { age: 20 }
var b = { name: 'sky', a: a }
a.b = b
function getCheckFunc(target) {
    var map = new Map()
    function checkCircle() {
        var keys = Object.keys(target)
        for(var i = 0; i < keys.length; i++) {
            var value = target[keys[i]]
            if(typeof value === 'object') {
                if(map.get(value)) {
                    return true
                } else {
                    map.set(value, 1)
                }
                return checkCircle(value)
            }
        }
        return false
    }
    return checkCircle
}

Share

暂时没有好的分享的点！