使用多个指针作为解决方案的 averagePair 问题

Question

我正在尝试解决以下问题：

到目前为止我想出了什么：

function averagePair(arr,tar){

    if (arr.length < 2){

        return false

    }

    let x = 0

    for (var y = 1; y < arr.length; y++){

        if ((arr[x] + arr[y]) / 2 == tar){

            return true

        }

        else {

            x++;

        }

    }

    return false

}

我知道这个解决方案不正确，有人可以解释为什么吗？它适用于某些情况但不是全部

Answer 1

有一个解决方案具有O(1)额外的空间复杂性和O(n)时间复杂性。由于数组已排序，因此有两个索引是有意义的：一个从数组的开头到结尾（比如y），另一个从数组的结尾到开头（比如x）。这是代码：function averagePair(arr,tar){&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; // That's now included in for-loop condition&nbsp; &nbsp; // if (arr.length < 2) {&nbsp; &nbsp; //&nbsp; &nbsp; &nbsp;return false;&nbsp; &nbsp; // }&nbsp; &nbsp; let x = arr.length - 1;&nbsp; &nbsp; for (var y = 0; y < x; y++) {&nbsp; &nbsp; &nbsp; &nbsp; // Division may lose precision, so it's better to compare&nbsp; &nbsp; &nbsp; &nbsp; //&nbsp; &nbsp;arr[x] + arr[y] > 2*tar&nbsp; &nbsp; &nbsp; &nbsp; // than&nbsp; &nbsp; &nbsp; &nbsp; //&nbsp; &nbsp;(arr[x] + arr[y]) / 2 > tar&nbsp; &nbsp; &nbsp; &nbsp; while (y < x && arr[x] + arr[y] > 2*tar) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; x--;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; if (x != y && arr[x] + arr[y] == 2*tar) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return false;}这是一种双指针技术：我们将减少x直到a[x] + a[y] > 2*tar当前循环迭代，因为我们需要找到最接近的匹配项。在下一个 for 循环迭代a[y]大于或等于前一个，因此检查是否a[z] + a[y] == 2*tar为 any是没有意义的z > x。我们将这样做直到索引不相等，这意味着没有匹配。

Answer 2

您只比较相邻的元素，例如[0]vs[1]和[1]vs [2]。您还需要比较[0]vs[2]等等。最简单的调整是使用嵌套循环：for (let x = 0; x < arr.length; x++) {&nbsp; for (let y = 0; y < arr.length; y++) {&nbsp; &nbsp; if (x !== y) {&nbsp; &nbsp; &nbsp; // test arr[x] against arr[y]但是使用 Set 来跟踪到目前为止发现的内容会更优雅且计算复杂性更低（O(n)而不是）：O(n ^ 2)const nums = new Set();for (const num of arr) {&nbsp; if (nums.has(tar - num)) {&nbsp; &nbsp; return true;&nbsp; } else {&nbsp; &nbsp; nums.add(num);&nbsp; }}function averagePair(arr,tar){&nbsp; const nums = new Set();&nbsp; for (const num of arr) {&nbsp; &nbsp; if (nums.has(tar - num)) {&nbsp; &nbsp; &nbsp; return true;&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; nums.add(num);&nbsp; &nbsp; }&nbsp; }&nbsp; return false;}console.log(averagePair([-2, 3, 2], 0));console.log(averagePair([-2, 3, 3], 0));