🥇用 JavaScript 解决 Google 面试问题：4 种不同的方式 |专业主机

当我研究算法的性能时，我遇到了这个这是谷歌模拟面试的视频。。它不仅让您了解大型科技公司的面试是如何进行的，还可以让您了解如何尽可能有效地解决算法问题。

这篇文章是视频的一种伴奏。在其中，我提供了对所显示的所有解决方案的评论，以及我自己的 JavaScript 解决方案版本。还讨论了每种算法的细微差别。

我们提醒： 对于“Habr”的所有读者 - 使用“Habr”促销代码注册任何 Skillbox 课程可享受 10 卢布的折扣。

技能箱推荐： 实践课程 “移动开发者专业版”.

制定问题

我们得到一个有序数组和一个特定值。然后要求创建一个函数，根据数组中任意两个数字的总和是否等于给定值，返回 true 或 false。

换句话说，数组中是否有两个整数 x 和 y，相加后等于指定值？

实施例A

如果给定一个数组 [1, 2, 4, 9] 并且值为 8，该函数将返回 false，因为数组中没有两个数字的和可以等于 8。

实施例B

但如果它是一个数组 [1, 2, 4, 4] 并且值为 8，则该函数应该返回 true，因为 4 + 4 = 8。

解决方案1：暴力破解

时间复杂度：O(N²)。
空间复杂度：O(1)。

最明显的含义是使用一对嵌套循环。

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      if (i !== j && arr[i] + arr[j] === val) {
        return true;
      };
    };
  };
  return false;
};

该解决方案效率不高，因为它检查数组中两个元素的每个可能的和，并将每对索引进行两次比较。（例如，当 i = 1 且 j = 2 时，实际上与与 i = 2 且 j = 1 进行比较相同，但在此解决方案中我们尝试了这两个选项）。

因为我们的解决方案使用一对嵌套的 for 循环，所以它是二次的，时间复杂度为 O(N²)。

解决方案2：二分查找

时间复杂度：O(Nlog(N))。
空间复杂度：O(1).

由于数组是有序的，因此我们可以使用二分搜索来搜索解决方案。这是有序数组最有效的算法。二分查找本身的运行时间为 O(log(N))。但是，您仍然需要使用 for 循环来根据所有其他值检查每个元素。

解决方案可能如下所示。为了清楚起见，我们使用一个单独的函数来控制二分搜索。还有removeIndex() 函数，它返回数组的版本减去给定的索引。

const findSum = (arr, val) => {
  for (let i = 0; i < arr.length; i++){
    if (binarySearch(removeIndex(arr, i), val - arr[i])) {
      return true;
    }
  };
  return false;
};
 
const removeIndex = (arr, i) => {
  return arr.slice(0, i).concat(arr.slice(i + 1, arr.length));
};
 
const binarySearch = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  let pivot = Math.floor(arr.length / 2); 
  while (start < end) {
    if (val < arr[pivot]) {
      end = pivot - 1;
    } else if (val > arr[pivot]) {
      start = pivot + 1;
    };
    pivot = Math.floor((start + end) / 2);
    if (arr[pivot] === val) {
      return true;
    }
  };
  return false;
};

该算法从索引[0]开始。然后，它创建一个不包括第一个索引的数组版本，并使用二分搜索来查看是否可以将任何剩余值添加到数组中以产生所需的总和。此操作对数组中的每个元素执行一次。

for 循环本身的线性时间复杂度为 O(N)，但在 for 循环内部我们执行二分搜索，这给出了 O(Nlog(N)) 的总体时间复杂度。该解决方案比前一种方案更好，但仍有改进的空间。

解决方案3：线性时间

时间复杂度：O(N)。
空间复杂度：O(1)。

现在我们将解决这个问题，记住数组是有序的。解决方案是取两个数字：一个在开头，一个在结尾。如果结果与要求的不同，则更改起点和终点。

最终我们要么遇到期望的值并返回 true，要么起点和终点收敛并返回 false。

const findSum = (arr, val) => {
  let start = 0;
  let end = arr.length - 1;
  while (start < end) {
    let sum = arr[start] + arr[end];
    if (sum > val) {
      end -= 1;
    } else if (sum < val) {
      start += 1;
    } else {
      return true;
    };
  };
  return false;
};

现在一切都很好，解决方案似乎是最佳的。但谁能保证数组是有序的呢？

什么呢？

乍一看，我们可以简单地先对数组进行排序，然后使用上面的解决方案。但这会如何影响执行时间呢？

最好的算法是快速排序，时间复杂度为O(Nlog(N))。如果我们在最优解决方案中使用它，它的性能将从 O(N) 变为 O(Nlog(N))。是否可以用无序数组找到线性解？

4解决方案

时间复杂度：O(N)。
空间复杂度：O(N)。

是的，有一个线性解决方案；为此，我们需要创建一个包含我们正在查找的匹配列表的新数组。这里的权衡是更多的内存使用：这是论文中空间复杂度大于 O(1) 的唯一解决方案。

如果给定数组的第一个值为 1 并且搜索值为 8，我们可以将值 7 添加到“搜索值”数组中。

然后，当我们处理数组的每个元素时，我们可以检查“搜索值”数组，看看其中一个是否等于我们的值。如果是，则返回true。

const findSum = (arr, val) => {
  let searchValues = [val - arr[0]];
  for (let i = 1; i < arr.length; i++) {
    let searchVal = val - arr[i];
    if (searchValues.includes(arr[i])) {
      return true;
    } else {
      searchValues.push(searchVal);
    }
  };
  return false;
};

该解决方案的基础是 for 循环，正如我们在上面看到的，它的线性时间复杂度为 O(N)。

我们函数的第二个迭代部分是 Array.prototype.include()，这是一个 JavaScript 方法，它将根据数组是否包含给定值返回 true 或 false。

要计算 Array.prototype.includes() 的时间复杂度，我们可以查看 MDN 提供的 polyfill（用 JavaScript 编写）或使用 JavaScript 引擎（例如 Google V8 (C++)）源代码中的方法。

// https://tc39.github.io/ecma262/#sec-array.prototype.includes
if (!Array.prototype.includes) {
  Object.defineProperty(Array.prototype, 'includes', {
    value: function(valueToFind, fromIndex) {
 
      if (this == null) {
        throw new TypeError('"this" is null or not defined');
      }
 
      // 1. Let O be ? ToObject(this value).
      var o = Object(this);
 
      // 2. Let len be ? ToLength(? Get(O, "length")).
      var len = o.length >>> 0;
 
      // 3. If len is 0, return false.
      if (len === 0) {
        return false;
      }
 
      // 4. Let n be ? ToInteger(fromIndex).
      //    (If fromIndex is undefined, this step produces the value 0.)
      var n = fromIndex | 0;
 
      // 5. If n ≥ 0, then
      //  a. Let k be n.
      // 6. Else n < 0,
      //  a. Let k be len + n.
      //  b. If k < 0, let k be 0.
      var k = Math.max(n >= 0 ? n : len - Math.abs(n), 0);
 
      function sameValueZero(x, y) {
        return x === y || (typeof x === 'number' && typeof y === 'number' && isNaN(x) && isNaN(y));
      }
 
      // 7. Repeat, while k < len
      while (k < len) {
        // a. Let elementK be the result of ? Get(O, ! ToString(k)).
        // b. If SameValueZero(valueToFind, elementK) is true, return true.
        if (sameValueZero(o[k], valueToFind)) {
          return true;
        }
        // c. Increase k by 1.
        k++;
      }
 
      // 8. Return false
      return false;
    }
  });
}

这里 Array.prototype.include() 的迭代部分是步骤 7 中的 while 循环，它（几乎）遍历给定数组的整个长度。这意味着它的时间复杂度也是线性的。好吧，由于它总是落后我们的主数组一步，所以时间复杂度是 O(N + (N - 1))。使用 Big O 表示法，我们将其简化为 O(N) - 因为在增加输入大小时，N 的影响最大。

关于空间复杂度，需要一个额外的数组，其长度镜像原始数组（负一，是的，但可以忽略），导致空间复杂度为 O(N)。那么，增加内存使用量可以确保算法的最大效率。

我希望您发现这篇文章作为视频采访的补充很有用。它表明一个简单的问题可以通过使用不同数量的资源（时间、内存）以多种不同的方式来解决。

技能箱推荐：

应用在线课程《Python数据分析师》.

在线课程《职业前端开发人员》.

实践年课程《PHP 开发者从 0 到 PRO》.

来源： habr.com

用 JavaScript 解决 Google 面试问题：4 种不同的方法

制定问题

什么呢？

添加评论取消回复

用 JavaScript 解决 Google 面试问题：4 种不同的方法

制定问题

什么呢？

添加评论 取消回复

添加评论取消回复