Pairwise求和问题优化：如何避免嵌套循环，降低时间复杂度？

嘿，你的嵌套循环解法逻辑是对的，但确实可以用哈希表（JS里的Map）把时间复杂度从O(n²)甚至更高降到O(n)，而且能完美满足题目里「优先使用最小可用索引」「不重复使用索引」的要求。我来一步步给你拆解：

先说说原解法的小优化 #

你原来用usedIndex.indexOf检查索引是否被使用，这个操作是O(n)的，再加上嵌套循环的O(n²)，实际最坏情况下复杂度是O(n³)。一个简单的小优化是把usedIndex换成Set，这样检查是否用过的时间变成O(1)，而且找到第一个符合条件的j就可以break，减少无效循环：

function pairwise(arr, arg) {
  const used = new Set();
  let output = 0;
  for (let i = 0; i < arr.length; i++) {
    if (used.has(i)) continue;
    for (let j = i + 1; j < arr.length; j++) {
      if (!used.has(j) && arr[i] + arr[j] === arg) {
        used.add(i);
        used.add(j);
        output += i + j;
        break; // 找到最小可用的j就停止，符合题目要求
      }
    }
  }
  return output;
}

真正的O(n)哈希表解法 #

如果想要彻底摆脱嵌套循环，我们可以用Map来记录未找到配对的元素的索引列表，同时用一个指针标记每个列表中第一个未被使用的索引，这样就能在一次遍历中完成所有配对：

function pairwise(arr, arg) {
  const indexMap = new Map();
  let result = 0;

  for (let i = 0; i < arr.length; i++) {
    const currentNum = arr[i];
    const complement = arg - currentNum;

    // 检查是否有可用的补数配对
    if (indexMap.has(complement)) {
      const { indices, start } = indexMap.get(complement);
      // 如果补数还有未被使用的索引
      if (start < indices.length) {
        const pairedIndex = indices[start];
        result += i + pairedIndex;
        // 移动指针，标记该索引已被使用
        indexMap.get(complement).start += 1;
        // 如果该补数的索引都用完了，从Map中移除
        if (indexMap.get(complement).start === indices.length) {
          indexMap.delete(complement);
        }
        // 找到配对后，不用把当前索引存进Map
        continue;
      }
    }

    // 没有找到配对，把当前索引存进Map
    if (!indexMap.has(currentNum)) {
      indexMap.set(currentNum, { indices: [], start: 0 });
    }
    indexMap.get(currentNum).indices.push(i);
  }

  return result;
}

核心逻辑拆解 #

1. 预存未配对索引：遍历数组时，先把找不到补数的元素索引按值存在Map里，每个值对应一个索引数组和一个start指针（标记第一个未被使用的索引）。
2. 快速找配对：对每个元素，计算需要的补数，如果补数在Map里且还有可用索引，就取出最早的那个索引（满足优先最小可用的要求），把两个索引的和加到结果里，同时标记该索引已被使用。
3. 避免重复使用：start指针只会向前移动，不会回头，确保每个索引只会被配对一次。

测试你的例子 #

比如pairwise([0, 0, 0, 0, 1, 1], 1)的运行过程：

• 前4个0都找不到补数1，被存在Map里：0: { indices: [0,1,2,3], start: 0 }
• 第5个元素是1，补数是0，Map里有0且start=0，取出索引0，结果加4+0=4，start变成1。
• 第6个元素是1，补数是0，Map里0的start=1，取出索引1，结果加5+1=6，总结果是10，完全符合预期。

这个解法的时间复杂度是严格的O(n)，每个元素只被遍历一次，所有Map操作都是O(1)，比嵌套循环高效得多，尤其是处理大型数组时。

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