求AdventJS首日挑战：数组首个重复数字的更优实现方案

我正在做AdventJS的每日挑战，已经完成首日任务——实现了查找数组中第一个重复数字的函数，能正常运行，但想找到更优的实现方式。

我的当前实现代码：

function findFirstRepeated(gifts) {
  let indexOfDup = null;
  let duplicated = -1;

  for (let i = 0; i < gifts.length; i++) {
        for (let j = i + 1; j < gifts.length; j++) {
          if (gifts[i] == gifts[j]) {
            if (indexOfDup == null || indexOfDup > j) {
              indexOfDup = j;
              duplicated = gifts[i];
            }
          }            
        }
  }
  return duplicated;
}

题目要求 #

北极玩具工厂的每个玩具都有唯一识别编号，因机器故障，部分编号被分配给多个玩具。请找出首个重复的识别编号，要求该编号的第二次出现索引最小；若存在多个重复编号，返回第二次出现最早的那个；若无重复编号，返回-1。

测试用例 #

const giftIds = [2, 1, 3, 5, 3, 2]
const firstRepeatedId = findFirstRepeated(giftIds)
console.log(firstRepeatedId) // 3
// 尽管2和3都重复，但3的第二次出现更早

const giftIds2 = [1, 2, 3, 4]
const firstRepeatedId2 = findFirstRepeated(giftIds2)
console.log(firstRepeatedId2) // -1
// 无重复编号，返回-1

const giftIds3 = [5, 1, 5, 1]
const firstRepeatedId3 = findFirstRepeated(giftIds3)
console.log(firstRepeatedId3) // 5

优化方案 #

方案1：使用Set实现线性时间复杂度 #

原代码采用双重循环，时间复杂度为O(n²)，当数组规模较大时效率较低。使用Set可以将时间复杂度优化到O(n)，空间复杂度为O(n)：

function findFirstRepeated(gifts) {
  const seen = new Set();
  for (const id of gifts) {
    if (seen.has(id)) {
      return id;
    }
    seen.add(id);
  }
  return -1;
}

思路说明：遍历数组时，用Set记录已经见过的编号。每遇到一个编号，先检查是否在Set中：如果存在，说明这是该编号的第二次出现，且因为是顺序遍历，这个就是第二次出现索引最小的重复编号，直接返回；如果不存在，就将其加入Set。遍历结束后若未找到重复，返回-1。

方案2：使用普通对象实现 #

如果环境不支持Set，也可以用普通对象来记录已遍历的编号，逻辑和Set一致：

function findFirstRepeated(gifts) {
  const seen = {};
  for (const id of gifts) {
    if (seen[id]) {
      return id;
    }
    seen[id] = true;
  }
  return -1;
}

这两种方案都能满足题目要求，且效率远高于原双重循环实现，尤其适合处理大规模数组。

内容的提问来源于stack exchange，提问作者Sofia Chardin