在二维数组中查找子二维数组的索引问题排查

问题描述 #

尝试在二维数组中查找目标子二维数组的首个起始索引，示例如下：

let board = [
  [ '0', '0', '0', '0' ],
  [ '1', '1', '1', '1' ],
  [ '2', '3', '3', '4' ]
]

let toFind = [ [ '1', '1' ], [ '4' ] ]

预期返回结果为[1,2]，但当前实现返回了[1,0]，问题出在checkMatch函数中。

当前实现的代码：

遍历查找函数findIndex #

const findIndex = (toFind, board) => {
  let results = [];
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] == toFind[0][0]) {
        if (checkMatch(board, toFind, i, j)) {
          console.log("Match Found");
          results.push([i, j]);
          return results;
        }
      }
    }
  }
  console.log("Not found");
};

匹配验证函数checkMatch #

const checkMatch = (board, toFind, row, col) => {
  let match = true;
  for (let i = row; i < toFind.length; i++) {
    for (let j = col; j < toFind[i].length; j++) {
      if (toFind[i - row][j - col] != board[i][j]) {
        match = false;
      }
    }
  }
  console.log(match);
  return match;
};

错误分析 #

checkMatch函数存在以下核心问题：

• 循环范围完全错误：外层循环用i < toFind.length作为终止条件，当起始行row大于0时（比如示例中的1），循环次数不足，遍历不完toFind的所有行；内层循环用board的行索引去取toFind的列长度，导致列遍历范围完全偏离。
• 无边界检查：没有验证row + toFind行数是否超出board的总行数，也没检查col + toFind当前行列数是否超出对应board行的列数，会导致越界访问或错误匹配。
• 匹配失败未及时终止：即使发现元素不匹配，仍继续循环，既降低效率，逻辑也不严谨。

修正后的代码 #

修正后的checkMatch函数 #

const checkMatch = (board, toFind, row, col) => {
  // 先检查起始位置能否容纳整个目标数组
  if (row + toFind.length > board.length) {
    return false;
  }
  for (let tfRow = 0; tfRow < toFind.length; tfRow++) {
    const boardRow = row + tfRow;
    // 检查当前board行是否有足够列数容纳目标数组的当前行
    if (col + toFind[tfRow].length > board[boardRow].length) {
      return false;
    }
    for (let tfCol = 0; tfCol < toFind[tfRow].length; tfCol++) {
      const boardCol = col + tfCol;
      if (toFind[tfRow][tfCol] !== board[boardRow][boardCol]) {
        // 发现不匹配立即返回，无需继续检查
        return false;
      }
    }
  }
  return true;
};

优化后的findIndex函数 #

const findIndex = (toFind, board) => {
  // 处理目标数组为空的边界情况
  if (!toFind.length || !toFind[0].length) {
    return null;
  }
  for (let i = 0; i < board.length; i++) {
    for (let j = 0; j < board[i].length; j++) {
      if (board[i][j] === toFind[0][0]) {
        if (checkMatch(board, toFind, i, j)) {
          console.log("Match Found");
          return [i, j];
        }
      }
    }
  }
  console.log("Not found");
  return null;
};

调用findIndex(toFind, board)会正确返回[1,2]。

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