求两个数组的交集

[Inchill]

有这样两个 number 类型的数组，需要求两个数组之间的交集。如果不借助 API，最先想到的是通过 for 循环来解决。

function findCommon (arr1, arr2) {
  var arr = []
  for (var i = 0; i < arr1.length; i++) {
    for (var j = 0; j < arr2.length; j++) {
      if (arr1[i] === arr2[j]) arr.push(arr1[i]) 
    }
  }
  return arr
}

这样虽然能满足要求，但是太原始了，时间复杂度始终是 O(m*n)。所以优化的点就是把时间复杂度 O(m*n) 给 降低到 O(m+n)。

因此想到了滑动比较，滑动比较需要对数组排序，这样才好利用排序的特征。滑动比较的具体操作是，采用双下标或者双指针，从头开始比较。如果一个值比另一个小，那么只需要移动小的那个的下标或者指针；如果两个值相等，那么这个值在交集里，保存该值，然后下表或者指针同时往前移动；重复前两步操作，直到下标或者指针超过数组长度为止。

有了这样的思路，接下来就是具体的编码实现了。第一步需要对数组进行排序，这里对两个数组进行升序排序。

function findCommon (arr1 = [], arr2 = []) {
  arr1 = arr1.sort((a, b) => a - b)
  arr2 = arr2.sort((a, b) => a - b)

  var i = 0,
    j = 0,
    arr = []

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      i++
    } else if (arr1[i] === arr2[j]) {
      arr.push(arr1[i])
      i++
      j++
    } else {
      j++
    }
  }

  return arr
}

由于多了一步排序操作，所以整体的复杂度，还需要加上 sort 方法的时间复杂度。对于 sort 这个 API，不同浏览器厂商的实现方式不一样，具体可以查看深入浅出 JavaScript 的 Array.prototype.sort 排序算法。