Leetcode整数序列解法中Time Limit Exceeded错误排查

超时核心原因 #

你的代码逻辑是逐个拼接数字成字符串，直到字符串长度满足n的要求，这种写法在n较小时没问题，但面对LeetCode的大测试用例（比如n接近2^31）时会直接超时，问题出在两点：

• 时间效率极低：字符串拼接是O(k)操作（k为当前字符串长度），每次循环都要复制整个现有字符串再追加新数字，时间复杂度达到O(n²)。当n是1e9级别的时候，这个循环要执行数百万次，每次的拼接成本越来越高，完全无法在时间限制内完成。
• 空间浪费严重：生成的超大字符串会占用巨量内存（比如n=1e9时，字符串长度接近1e9，内存占用以GB计），内存压力会进一步拖慢程序运行速度。

优化思路：数学定位，无需生成完整序列 #

不用实际拼接字符串，通过数学计算直接定位到第n位所在的数字和具体位置：

1. 确定目标数字的位数：先划分位数区间，比如1位数（1-9）占9位，2位数（10-99）占180位，3位数（100-999）占2700位... 逐步减去这些区间的总位数，直到找到n所在的位数区间。
2. 定位具体数字：在确定的位数区间内，计算出n对应的具体数字。
3. 提取目标位：找到该数字中对应的那一位，直接返回。

优化后的代码示例（Dart） #

class Solution {
  int findNthDigit(int n) {
    if (n <= 0) return 0;
    int digitLength = 1;
    int count = 9;
    int start = 1;

    // 定位n所在的数字位数区间
    while (n > digitLength * count) {
      n -= digitLength * count;
      digitLength++;
      count *= 10;
      start *= 10;
    }

    // 找到目标数字
    int targetNum = start + (n - 1) ~/ digitLength;
    // 找到数字中的目标位置
    int position = (n - 1) % digitLength;
    // 提取该位数字
    return int.parse(targetNum.toString()[position]);
  }
}

这个优化后的代码时间复杂度是O(log n)，循环次数仅与数字的位数有关（最多10次左右），空间复杂度O(1)，完全能处理超大n的测试用例。

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