我正在尝试返回一个值索引数组，这些索引加起来就是一个给定的目标。我正在尝试以最快的方式解决它！
例子：
sumOfTwo([1, 2, 4, 4], 8) // => [2, 3]
sumOfTwo([1, 2, 3, 9], 8) // => []
所以首先我尝试了一个简单的蛮力。(时间复杂度：O(n^2) )
function sumOfTwo(arr, target) {
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
if (arr[i] + arr[j] === target) {
return [i, j];
}
}
}
return [];
}
然后我尝试：(时间复杂度：排序O(n logn) + for 循环O(n))
function sumOfTwo(arr, target) {
const sortedArr = arr.sort();
let idxFromBack = arr.length - 1;
for (let [idx, val] of sortedArr.entries()) {
if (val + arr[idxFromBack] > target) {
idxFromBack--;
}
if (val + arr[idxFromBack] === target) {
return [idx, idxFromBack];
}
}
return [];
}
然后我提出了这个解决方案，我什至不知道时间复杂度。
function sumOfTwo(arr, target) {
const complements = [];
for (let [idx, val] of arr.entries()) {
if (complements.reduce((acc, v) => (acc || v.value === val), false)) {
return [complements.find(v => v.value === target - val).index, idx];
}
complements.push({index: idx, value: target - val});
}
return [];
}
我知道我正在使用for循环，但我不知道内置高阶函数.reduce()和.find()的复杂性。我尝试了几次搜索，但找不到任何东西。
如果有人能帮助我，那就太好了！如果可能，请包括 Big-O 表示法。
Repl.it：https://repl.it/@abranhe/sumOfTwo
还请包括最后一个解决方案的时间复杂度。
.reduce的最小时间复杂度是O(n)，因为它必须遍历所有元素一次(假设没有抛出错误)，但它可以是无限的(因为你可以在回调中编写任何你想要的代码)。
为了您的
// Loop, O(n), n = length of arr:
for (let [idx, val] of arr.entries()) {
// .reduce, O(n), n = length of complements:
if (complements.reduce((acc, v) => (acc || v.value === val), false)) {
// If test succeeds, .find, O(n), n = length of complements:
return [complements.find(v => v.value === target - val).index, idx];
}
complements.push({index: idx, value: target - val});
}
最坏情况下，时间复杂度为O(n^2)。reduce在O(n)时间内运行，您可以为arr中的每个条目运行reduce，使其O(n^2)。
(.find也是O(n)操作，但O(n)+O(n)=O(n))
事先对数组进行排序的代码具有降低复杂性的正确想法，但它有几个缺陷。
首先，您应该按数字排序(
(a, b) => a - b)); 没有参数.sort()将按字典顺序排序(例如，[1, 11, 2]是不可取的)。其次，仅仅减少
idxFromBack是不够的：例如，sumOfTwo([1, 3, 8, 9, 9], 9)不会看到 1 和 8 是匹配的。也许这里最好的策略是随while振荡：从idxFromBack向后迭代，直到找到匹配项或总和太小，并且向前迭代直到找到匹配项或总和太大。
您还可以通过不使用具有O(n log n)复杂度的.sort((a, b) => a - b)进行排序，而是使用基数排序或计数排序(两者都具有O(n + k)的复杂性，其中k是一个常数)来提高此代码的性能。最佳算法将取决于输入的一般形状和方差。
一个更好的，完全不同的O(n)策略是使用地图或对象。遍历数组时，将将导致当前项匹配的值放入对象的键中(其中值是当前索引)，然后查看正在迭代的当前值最初是否存在于对象中：
const sumOfTwo = (arr, target) => {
const obj = {};
for (const [i, num] of arr.entries()) {
if (obj.hasOwnProperty(String(num))) {
return [obj[num], i];
}
const matchForThis = target - num;
obj[matchForThis] = i;
}
return [];
};
console.log(
sumOfTwo([1, 2, 4, 4], 8), // => [2, 3]
sumOfTwo([1, 2, 8, 9], 9), // 1 + 8 = 9; [0, 2]
sumOfTwo([1, 2, 3, 9], 8) // => []
);作为补充答案，以下是语言规范中find方法的算法：
调用 find 方法时，将执行以下步骤：
让 O 成为 ？ToObject(此值)。
让伦成为？LengthOfArrayLike(O).
如果 IsCallable(谓词)为 false，则引发 TypeError 异常。
设 k 为 0。
重复，当 k <len，>
一个。让 Pk 成为 ！ToString(F(k)).
二.让kValue成为？Get(O， Pk).
三.让测试结果是！ToBoolean(？Call(谓词， thisArg， « kValue， F(k)， O »)).
d.如果 testResult 为 true，则返回 kValue。
e. 将 k 设置为 k + 1。
返回未定义。
请注意步骤 5 中的"重复，而 k
在步骤 5 中进行的迭代次数等于len，这直接取决于集合中的元素数量。什么时间复杂度与元素的数量有直接关系？确切地说，线性 O(n)。
对于视觉演示，请运行以下代码片段。除了一些杂散的点外，即兴图形应该显示线性进展(在 Stack 片段中显示需要一点时间，但您可以在 devtools 控制台中实时观看)：
const iter = 1e7;
const incr = 2e5;
const test = new Array(iter).fill(0);
const steps = Math.ceil(iter / incr);
for (let i = 0; i < steps; i += 1) {
const sub = test.slice(0, i * incr + incr);
const s = Date.now();
const find = sub.find((v) => v === 1);
const e = Date.now();
const d = e - s;
console.log("u200A".repeat(Math.floor(d/3))+"*");
}