指定区间内同数字自然数生成算法及内存优化求助

原问题与痛点 #

需求是统计区间[l, r]内所有由相同数字组成的自然数个数（例如999999符合要求，123123不符合），输入范围为1 ≤ l,r ≤ 10^18，内存限制256MB。

当前代码因内存占用超标（实际565.56MB）无法通过测试，原代码如下：

function numberOfTests(l, r) {
  let count = 0;

  for (let i = l; i <= +r; i++) {
    let el = String(i).split("");
    el = [el.every((e, i, a) => e === a[0])];
    if (!el.includes(false)) {
      count++;
    }
  }
  return count;
}

console.log(numberOfTests("10 100")); // 9
console.log(numberOfTests("4 7")); // 4

原代码问题分析 #

• 遍历范围过大：当r达到10^{18时，循环需要执行10}18次，这不仅极端耗时，还会频繁创建字符串、数组等临时对象，导致内存堆积。
• 内存浪费严重：每次循环都将数字转换为字符串、拆分为数组，大量临时对象无法及时回收，直接导致内存占用超出限制。

优化思路与算法逻辑 #

符合条件的数是固定模式的：1-9（1位）、11-99（2位）、111-999（3位）……直到18位的999...999。这类数的总量非常少，仅9*18=162个（1-9每个数字对应1到18位的数）。

核心优化思路：直接生成所有符合条件的数，再统计其中落在[l, r]区间内的数量，无需遍历区间内所有数。

具体步骤：

1. 对每个数字d（1到9），依次生成1位、2位……直到18位的同数字数（例如d=3时，生成3、33、333……）。
2. 逐个判断生成的数是否在[l, r]范围内，统计符合条件的数量。

优化后的代码 #

function numberOfTests(input) {
  const [lStr, rStr] = input.split(' ');
  const l = BigInt(lStr);
  const r = BigInt(rStr);
  let count = 0;

  // 遍历1-9每个基础数字
  for (let d = 1; d <= 9; d++) {
    let current = BigInt(d);
    // 生成1到18位的同数字数
    for (let len = 1; len <= 18; len++) {
      if (current >= l && current <= r) {
        count++;
      }
      // 生成下一位的同数字数
      const next = current * 10n + BigInt(d);
      // 若下一个数已超过r，无需继续生成当前数字的更长位数
      if (next > r) {
        break;
      }
      current = next;
    }
  }

  return count;
}

console.log(numberOfTests("10 100")); // 9
console.log(numberOfTests("4 7")); // 4

代码细节说明 #

• 使用BigInt处理超大数：由于输入范围到10^{18，超过了JavaScript普通Number的精确范围（最大精确到2}53≈9e15），必须用BigInt避免精度丢失。
• 提前终止循环：当生成的数超过r时，立即停止当前数字的后续生成，减少不必要的计算。
• 低内存占用：全程通过数值计算生成目标数，无需创建大量字符串、数组等临时对象，内存占用远低于256MB限制。

内容的提问来源于stack exchange，提问作者Роман