使用多个指针作为解决方案的 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

您只比较相邻的元素，例如 [0] 与 [1]，以及 [1] 与 [2]。您还需要比较 [0] 与 [2] 等等。最简单的调整是使用嵌套循环：

for (let x = 0; x < arr.length; x++) {
  for (let y = 0; y < arr.length; y++) {
    if (x !== y) {
      // test arr[x] against arr[y]

但是使用 Set 来跟踪到目前为止发现的内容会更优雅且计算复杂性更低（O(n) 而不是 O(n ^ 2)）：

const nums = new Set();
for (const num of arr) {
  if (nums.has(tar - num)) {
    return true;
  } else {
    nums.add(num);
  }
}

function averagePair(arr,tar){
  const nums = new Set();
  for (const num of arr) {
    if (nums.has(tar - num)) {
      return true;
    } else {
      nums.add(num);
    }
  }
  return false;
}

console.log(averagePair([-2, 3, 2], 0));
console.log(averagePair([-2, 3, 3], 0));

Answer 2

有一个解决方案 O(1) 额外 space 复杂度和 O(n) 时间复杂度。

因为一个数组是排序的，所以有两个索引是有意义的：一个从头到尾（比如y），另一个从数组的尾到头（比如x） .

代码如下：

function averagePair(arr,tar){
    
    // That's now included in for-loop condition
    // if (arr.length < 2) {
    //     return false;
    // }

    let x = arr.length - 1;

    for (var y = 0; y < x; y++) {

        // Division may lose precision, so it's better to compare
        //   arr[x] + arr[y] > 2*tar
        // than
        //   (arr[x] + arr[y]) / 2 > tar

        while (y < x && arr[x] + arr[y] > 2*tar) {
            x--;
        }
        if (x != y && arr[x] + arr[y] == 2*tar) {
            return true;
        }
    }
    return false;
}

这是一种 two-pointers 技术：我们将减少 x 直到当前循环迭代 a[x] + a[y] > 2*tar，因为我们需要找到最接近的匹配项。在下一个 for-loop 迭代中 a[y] 大于或等于前一个迭代，因此检查任何 z > x 是否为 a[z] + a[y] == 2*tar 是没有意义的。我们将这样做直到索引不相等，这意味着没有匹配项。

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

averagePair problem using multiple pointers as a solution

javascript

algorithm

pointers

average