在研究算法性能时，我
从Google的模拟采访中看到了
这段视频 。 它不仅给出了大型技术公司如何进行面试的想法，而且还使您了解如何最有效地解决算法问题。
本文是对视频的一种伴奏。 在其中，我对显示的所有解决方案以及我自己的JavaScript版本进行评论。 还讨论了每种算法的细微差别。
我们提醒您： 对于所有“哈勃”读者来说，使用“哈勃”促销代码注册任何Skillbox课程时均可享受10,000卢布的折扣。
Skillbox建议：实用课程“ Mobile Developer PRO” 。
问题陈述
给我们一个有序的数组和一个特定的值。 然后，他们要求创建一个返回true或false的函数，具体取决于数组中任何两个数字的总和是否可以等于给定值。
换句话说，数组中是否存在两个整数x和y，它们相加时等于指定的值？
例子A如果给我们一个数组[1、2、4、9]和一个值为8，则该函数将返回false，因为数组中的两个数字之和不能为8。
例子B但是，如果它是一个数组[1、2、4、4]，并且值为8，则该函数应返回true，因为4 + 4 = 8。
解决方案1. Bruteforce时间上的困难：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（对数（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（使用JavaScript编写）提供的polyfill，或使用JavaScript引擎的源代码中的方法，例如Google V8（C ++）。
在这里，Array.prototype.include（）的迭代部分是步骤7中的while循环，该循环（几乎）遍历给定数组的整个长度。 这意味着其时间复杂度也是线性的。 好吧，由于它总是比我们的主数组落后一步，因此时间复杂度为O（N +（N-1））。 使用大O表示法，我们将其简化为O（N）-因为随着输入大小的增加，影响最大的是N。
关于空间复杂度，需要一个额外的数组，其长度反映原始数组（减去一个，是的，但这可以忽略），这导致空间复杂度O（N）。 好吧，增加的内存使用量可以确保最大的算法效率。
希望本文作为视频采访的附件对您有所帮助。 它显示了一个简单的问题可以用几种不同的方式使用不同的资源（时间，内存）来解决。
Skillbox建议：