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

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

标签： javascriptalgorithmpointersaverage

Answer 1

您只是在比较相邻元素，例如[0]vs[1]和[1]vs [2]。你还需要比较[0]vs[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));