JS数组高效查找指定起始与结束字符的索引对

在JavaScript数组处理过程中，我们经常遇到一个看似简单却暗藏细节的问题：如何高效地找出所有符合特定前后顺序的字符索引对？具体来说，给定一个数组以及两个目标字符（例如起始字符 'a' 和结束字符 'c'），我们需要返回所有满足 i < j 且 arr[i] 为起始字符、arr[j] 为结束字符的索引对 [i, j]。

这并非简单地找到第一个 'a' 和第一个 'c' 就完成了任务。真正的需求是“穷举”——出现在前面的每一个 'a' 都必须与其之后的所有 'c' 逐一配对。

通过一个例子可以更清晰地理解。假设数组为 ['a', 'b', 'c', 'd', 'e', 'a', 'c']，那么：

• 所有 'a' 位于索引 0 和 5。
• 所有 'c' 位于索引 2 和 6。

合法配对要求 'a' 在 'c' 之前，因此有效的组合是：

• 0 → 2 (0 < 2)
• 0 → 6 (0 < 6)
• 5 → 6 (5 < 6)

注意，索引 5 的 'a' 不能与索引 2 的 'c' 配对，因为 5 > 2，顺序错误。这也意味着，绝不能想当然地将第一个 'a' 与第一个 'c' 配对、第二个 'a' 与第二个 'c' 配对，那样会遗漏大量组合。正确的做法必须基于完整的笛卡尔积并加以条件过滤。

清晰高效的推荐解法：双指针与索引预收集

最直观、最容易理解和维护的方法，是分两步走：先收集，再组合。

function findAllIndexPairs(arr, startChar, endChar) {
  const starts = [];
  const ends = [];
  // 第一步：遍历一次，分别收集所有起始和结束字符的索引
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === startChar) starts.push(i);
    else if (arr[i] === endChar) ends.push(i);
  }
  const pairs = [];
  // 第二步：对收集到的索引进行双层循环，筛选出 i < j 的组合
  for (const i of starts) {
    for (const j of ends) {
      if (i < j) pairs.push([i, j]);
    }
  }
  return pairs;
}

// 示例调用
const arr = ['a', 'b', 'c', 'd', 'e', 'a', 'c'];
console.log(findAllIndexPairs(arr, 'a', 'c'));
// 输出: [[0, 2], [0, 6], [5, 6]]

该方案的时间复杂度为 O(n + s×e)，其中 n 是数组长度，s 和 e 分别是起始字符和结束字符出现的次数。空间复杂度为 O(s + e)。它的最大优势是逻辑极为清晰，便于调试、测试和后续扩展，在绝大多数场景下性能已经足够出色。

关于一种常见误解的说明

在讨论此问题时，有时会遇到一种试图“边遍历边配对”的解法，例如使用 reduce 配合动态对象来聚合状态。这类解法初衷良好，希望一次遍历解决问题，但其逻辑往往存在一个关键偏差：它可能隐含地假设每个起始字符只匹配“最近”的一个结束字符，或试图在同一个聚合对象内完成配对。

这会导致什么问题呢？沿用之前的数组为例，这种实现很可能只输出 [0, 2] 和 [5, 6]，而遗漏了 [0, 6] 这个同样合法的组合。因为它没有考虑到，一个出现在前面的起始字符，可以匹配其后出现的所有结束字符。所以，这类解法通常不符合“找出所有配对”的原始问题语义，需要特别注意甄别。

进阶优化思路

当然，如果面对超大型数组且目标字符非常稀疏，我们还可以考虑进一步优化。思路是：在遍历数组寻找起始字符时，一旦找到一个，就从一个预先收集好的、有序的结束字符索引列表中，快速找出所有大于当前索引的结束位置。

function findAllIndexPairsOptimized(arr, startChar, endChar) {
  const pairs = [];
  // 预先收集所有结束字符的索引
  const endIndices = arr.map((c, i) => c === endChar ? i : -1)
                        .filter(i => i !== -1);
  // 遍历数组
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === startChar) {
      // 对于每个起始字符，遍历所有结束索引，只保留位置在后的
      for (const j of endIndices) {
        if (j > i) pairs.push([i, j]);
      }
    }
  }
  return pairs;
}

如果对性能有极致要求，甚至可以将 endIndices 的查找部分改为二分搜索，以快速定位第一个大于 i 的结束索引，从而避免无效遍历。不过，在字符出现次数不多的情况下，简单的线性遍历通常已经足够快。

总结与建议

• 首选方案：采用“分步收集索引 + 嵌套循环过滤”的方法。它的代码简洁，语义明确，是平衡可读性、可维护性和执行效率的最佳选择。
• 核心陷阱：务必避免任何形式的“贪心配对”逻辑，确保算法能够覆盖所有满足 i < j 条件的组合。
• 扩展思考：如果问题演变为需要匹配更长的字符序列（例如 'a'→'b'→'c'），可以将当前思路泛化，使用滑动窗口或动态规划的逻辑来处理。
• 工程实践：在生产代码中，建议增加基础的输入校验，例如检查输入是否为数组、目标字符是否有效等，以提升函数的鲁棒性。