如何使用JavaScript查找字符串中块符号[和]的对应配对索引

实现思路 #

这个需求完全可以实现，最简洁高效的方案是使用嵌套计数法，不需要额外存储所有括号的位置，单次遍历即可得到结果，时间复杂度为O(n)，空间复杂度为O(1)。
具体逻辑如下：

• 首先做入参校验：先判断传入索引位置的字符是不是[或者]，如果不是直接返回-1作为非法标识
• 如果目标字符是左括号[：
  1. 初始化嵌套计数为1，从目标索引的下一位开始向后遍历字符串
  2. 每遇到一个[就将计数+1（代表嵌套层级加1），每遇到一个]就将计数-1（代表嵌套层级减1）
  3. 当计数降到0的时候，当前遍历到的索引就是配对的右括号位置
  4. 如果遍历完整个字符串计数还没到0，说明没有配对的右括号，返回-1
• 如果目标字符是右括号]：
  1. 初始化嵌套计数为1，从目标索引的前一位开始向前遍历字符串
  2. 每遇到一个]就将计数+1，每遇到一个[就将计数-1
  3. 当计数降到0的时候，当前遍历到的索引就是配对的左括号位置
  4. 如果遍历完整个字符串计数还没到0，返回-1

完整代码实现 #

function getBlock(str, targetIndex) {
  // 入参边界校验
  if (targetIndex < 0 || targetIndex >= str.length) return -1
  const targetChar = str[targetIndex]
  if (targetChar !== '[' && targetChar !== ']') return -1

  let count = 1
  // 处理左括号匹配右括号的情况
  if (targetChar === '[') {
    for (let i = targetIndex + 1; i < str.length; i++) {
      if (str[i] === '[') count++
      if (str[i] === ']') count--
      if (count === 0) return i
    }
  } 
  // 处理右括号匹配左括号的情况
  else {
    for (let i = targetIndex - 1; i >= 0; i--) {
      if (str[i] === ']') count++
      if (str[i] === '[') count--
      if (count === 0) return i
    }
  }
  // 遍历完无匹配
  return -1
}

测试验证 #

用你给出的示例测试，结果完全符合预期：

var str = "abc [def [ghi [jkl]]]";
console.log(getBlock(str, 4)); // 输出20
console.log(getBlock(str, 9)); // 输出19
console.log(getBlock(str, 14)); // 输出18
console.log(getBlock(str, 20)); // 输出4
console.log(getBlock(str, 19)); // 输出9
console.log(getBlock(str, 18)); // 输出14

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