JavaScript二维数组查找优化：值3出现次数的高效实现

问题背景 #

现有二维数组，需要统计指定值的出现次数，当前采用扁平化数组的方式实现，时间复杂度为O(parentArraySize * subArraysSize)，且子数组长度不固定。需要适配多目标查询场景，不介意空间开销。

最优方案：预构建频率哈希表（空间换时间） #

直接预遍历整个二维数组，用哈希表记录每个元素的出现次数，后续所有查询都能在O(1)时间内完成，完美适配多目标查询需求。

代码实现（JavaScript）

const twoDArray = [[1, 2, 3], [3, 5, 7], [3, 9, 10]];
const frequencyMap = new Map();

// 预遍历构建频率映射表
for (const subArray of twoDArray) {
  for (const num of subArray) {
    frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
  }
}

// 查询单个目标值
console.log(frequencyMap.get(3)); // 输出：3

// 多目标查询示例
console.log(frequencyMap.get(1)); // 输出：1
console.log(frequencyMap.get(5)); // 输出：1
console.log(frequencyMap.get(10)); // 输出：1

方案分析

• 时间复杂度：预遍历阶段为O(m*n)（m为外层数组长度，n为子数组平均长度），后续所有查询均为O(1)，多目标场景下优势极大。
• 空间复杂度：O(k)，k为数组中不同元素的数量，完全符合“不介意空间开销”的要求。

补充方案：二分查找累加（适用于有序子数组） #

如果你的子数组是有序的，可以对每个子数组用二分查找定位目标值的首尾位置，计算单个子数组中的出现次数后累加。此方案不需要预存哈希表，但多目标查询时需重复执行遍历操作。

代码实现（JavaScript）

// 统计有序数组中目标值的出现次数
function countInSortedArr(arr, target) {
  let left = 0, right = arr.length - 1;
  let firstPos = -1;

  // 查找第一个目标值的位置
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      firstPos = mid;
      right = mid - 1;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  if (firstPos === -1) return 0;

  left = firstPos;
  right = arr.length - 1;
  let lastPos = firstPos;

  // 查找最后一个目标值的位置
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      lastPos = mid;
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return lastPos - firstPos + 1;
}

const twoDArray = [[1, 2, 3], [3, 5, 7], [3, 9, 10]];
const target = 3;
let totalCount = 0;

for (const subArr of twoDArray) {
  totalCount += countInSortedArr(subArr, target);
}

console.log(totalCount); // 输出：3

方案分析

• 时间复杂度：单次查询为O(m*log n)（m为外层数组长度，n为子数组平均长度），适合偶尔查询且子数组有序的场景。
• 空间复杂度：O(1)，无需额外存储频率数据。

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