将O(n²)复杂度的JS函数优化为O(n)：提取数组相同整数间的整数

你可以用哈希表（Map）结合队列来实现核心逻辑的单次遍历，避免嵌套循环。核心思路是记录每个元素待匹配的最早出现位置，当再次遇到相同元素时，直接提取两者之间的元素并完成匹配，同时将当前位置加入待匹配队列等待后续可能的匹配。

优化后的代码 #

const identical = (input) => {
  const result = [];
  // 用Map存储每个元素的待匹配索引队列，先进先出保证匹配最早的未处理位置
  const elementIndices = new Map();

  for (let currentIdx = 0; currentIdx < input.length; currentIdx++) {
    const currentVal = input[currentIdx];
    
    if (elementIndices.has(currentVal)) {
      const indicesQueue = elementIndices.get(currentVal);
      // 取出最早的待匹配索引
      const prevIdx = indicesQueue.shift();
      // 提取中间元素并加入结果
      result.push(...input.slice(prevIdx + 1, currentIdx));
    } else {
      // 首次出现该元素，初始化队列
      elementIndices.set(currentVal, []);
    }
    // 将当前索引加入队列，等待后续匹配
    elementIndices.get(currentVal).push(currentIdx);
  }

  return result;
};

// 测试示例
const input = [2, 3, 4, 2, 3, 5, 2];
console.log(identical(input)); // 输出: [3, 4, 4, 2, 3, 5]

逻辑说明 #

1. 数据结构选择：用Map存储每个元素对应的索引队列，队列的先进先出特性保证我们总是匹配当前元素最早出现的未处理位置，和原O(n²)解法的逻辑完全一致。
2. 遍历过程：
   • 每遇到一个元素，先检查是否有待匹配的历史索引：如果有，就取出最早的索引，提取两者之间的元素加入结果。
   • 无论是否匹配成功，都将当前索引加入该元素的待匹配队列，等待后续可能的相同元素匹配。
3. 复杂度分析：
   • 核心遍历是O(n)，每个索引只会入队和出队各一次，这部分是O(n)。
   • 提取中间元素的操作总时间是O(m)，其中m是所有中间元素的总长度，实际场景中比嵌套循环的O(n²)更高效，因为完全省去了内层循环的无意义比较。

和原解法的对比 #

原解法通过嵌套循环逐个查找每个元素的后续匹配项，会做大量重复比较；优化后的解法通过哈希表直接定位待匹配项，仅在需要提取中间元素时访问数组片段，逻辑更高效简洁。

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