寻求计算任意数组中两个1之间0的数量的简易算法

问题规则明确 #

只统计被两个1夹在中间的0：

• 数组第一个1之前的0、最后一个1之后的0不计入
• 如果数组中1的数量少于2，结果直接为0

实现思路与代码示例 #

思路1：单次遍历计数（空间高效）

遍历数组时，用状态标记是否进入“两个1之间”的计数阶段：

• 遇到第一个1时，开启计数状态
• 处于计数状态时，遇到0就累加当前段的0数量
• 再次遇到1时，将当前段的0数量计入总数，重置当前计数器，继续后续遍历

function countZerosBetweenOnes(arr) {
  let total = 0;
  let isCounting = false;
  let currentZeroCount = 0;

  for (const num of arr) {
    if (num === 1) {
      if (isCounting) {
        total += currentZeroCount;
        currentZeroCount = 0;
      } else {
        isCounting = true;
      }
    } else if (isCounting) {
      currentZeroCount++;
    }
  }

  return total;
}

思路2：收集1的索引计算（直观易懂）

先提取所有1在数组中的索引，再遍历相邻索引对，计算每对之间的元素数量（即两个1之间的0的数量）：

• 若1的索引数量少于2，直接返回0
• 相邻两个1的索引差减1，就是这段之间的0的数量，累加所有段的结果

function countZerosBetweenOnes(arr) {
  const onePositions = arr.reduce((acc, num, idx) => {
    if (num === 1) acc.push(idx);
    return acc;
  }, []);

  if (onePositions.length < 2) return 0;

  let total = 0;
  for (let i = 0; i < onePositions.length - 1; i++) {
    total += onePositions[i + 1] - onePositions[i] - 1;
  }

  return total;
}

测试验证 #

用给出的示例测试两种方法，结果均符合预期：

const mas1 = [0,1,0,0,1];
const mas2 = [1,0,0,0,1];
const mas3 = [0,1,0,1,0];
const mas4 = [0,0,0,0,1];
const mas5 = [1,0,1,0,1];

console.log(countZerosBetweenOnes(mas1)); // 2
console.log(countZerosBetweenOnes(mas2)); // 3
console.log(countZerosBetweenOnes(mas3)); // 1
console.log(countZerosBetweenOnes(mas4)); // 0
console.log(countZerosBetweenOnes(mas5)); // 2

方法对比 #

• 思路1：仅需一次遍历，空间复杂度O(1)，适合处理超大数组
• 思路2：逻辑直观易维护，空间复杂度O(k)（k为数组中1的数量），对常规规模数组友好

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