检查数组重复值的函数工作原理解析及相关疑问解答

问题描述 #

我有一段检查重复值的代码：

function hasDuplicateValue(array) {
  var existingNumbers = [];
  for (var i = 0; i < array.length; i++) {
    if (existingNumbers[array[i]] === undefined) {
      existingNumbers[array[i]] = 1;
    } else {
      return true;
    }
  }
  return false;
}

变量existingNumbers用于标记数组中的值，若找到数组中的值就将其设为1，若之前已见过该值则立即返回true。

我知道existingNumbers的所有值会从undefined变为1，但不清楚代码何时检查重复。比如如果我把else改为：

else if (existingNumbers[array[i]] !== undefined) {
    return true
}

existingNumbers的所有元素都是1，那是不是会总是返回true？我想知道else分支中触发返回true的具体条件是什么。

编辑补充：
我找到了更易理解的写法：

if (existingNumbers.includes(array[i])) {
      return true;
    } else {
      existingNumbers.push(array[i]);
    }

不过看到资料说.includes方法的时间复杂度是O(n)，那是不是之前的方法性能更好？至少这个写法帮助我理解了逻辑。

解答 #

1. 原代码的重复触发逻辑

原代码核心是用数组下标标记已出现的数值：

• 遍历数组时，把当前元素array[i]当作existingNumbers的下标访问
• 如果existingNumbers[array[i]]是undefined，说明该数值从未出现过，就把该下标位置的值设为1（做已出现标记）
• 只有当existingNumbers[array[i]]**不是undefined**时，才会进入else分支返回true——这意味着当前数值已经被标记过，也就是出现了重复。

举个实际例子：数组为[2, 3, 2]

• 第一次取元素2：existingNumbers[2]是undefined，设为1
• 第二次取元素3：existingNumbers[3]是undefined，设为1
• 第三次取元素2：existingNumbers[2]已经是1（不是undefined），触发else分支，返回true

2. 修改else分支后的疑问

你改成的else if (existingNumbers[array[i]] !== undefined)和原else分支逻辑完全等价。因为原if条件是existingNumbers[array[i]] === undefined，不满足这个条件时，必然就是existingNumbers[array[i]] !== undefined，所以不会“总是返回true”，只有数值重复时才会触发返回。这种写法属于冗余判断，完全没必要，原else分支已经能准确覆盖重复场景。

3. 两种写法的性能对比

没错，原方法的性能确实更好：

• 原方法利用数组下标访问（JS数组本质是特殊对象，下标访问属于对象属性访问），时间复杂度是O(1)，整个遍历的时间复杂度为O(n)
• .includes方法是遍历数组逐个比对元素，每次查找都要花O(n)的时间，整个遍历的时间复杂度会变成O(n²)——当数组元素数量大时，性能差距会非常显著

不过.includes的写法逻辑更直观，适合理解基础逻辑；如果追求性能，除了原方法，还可以用JS的Set结构，has方法的时间复杂度也是O(1)，代码更简洁：

function hasDuplicateValue(array) {
  const seen = new Set();
  for (const num of array) {
    if (seen.has(num)) {
      return true;
    }
    seen.add(num);
  }
  return false;
}

内容的提问来源于stack exchange，提问作者me-an-ape