2026-07-07：统计区间内奇妙数的数目。用go语言，给定两个整数 l 和 r。对于任意整数，把它写成十进制各位数字的序列：如果这些数字从左

2026-07-07：统计区间内奇妙数的数目。用go语言，给定两个整数 l 和 r。对于任意整数，把它写成十进制各位数字的序列：如果这些数字从左到右要么严格递增、要么严格递减（相邻两位必须分别满足更大或更小），则该整数称为 好数。任意一位的整数都算 好数。若某个整数是 好数，或它的各位数字之和本身是 好数，则该整数称为 奇妙数。需要计算区间 [l, r]（包含端点）中 奇妙数 的个数，并返回这个数量。

1 <= l <= r <= 1000000000000000。

输入： l = 8, r = 10。

输出： 3。

解释：

8 和 9 是一位数，所以它们是好数，因此也是奇妙数。

10 的数位为 [1, 0]，形成了一个严格递减的序列，所以 10 是好数，因此也是奇妙数。

因此，答案是 3。

题目来自力扣3869。

一、代码整体两大模块分步流程

整体分为两大独立计算模块，结果相加得到最终奇妙数总数：
模块A：预处理所有“本身是好数、且数位和不是好数”的数字，二分统计区间数量ans；
模块B：数位DP统计区间内所有数位和为好数的数字数量dfs结果；
最终答案 = A结果 + B结果。

模块A：预处理全部纯好数（本身是好数），快速区间计数 步骤1：初始化全局数组goodNums（init函数预生成，程序启动仅执行一次）

目标：枚举、生成所有十进制严格递增/严格递减的数字（全部好数），过滤掉其中数位和为好数的数字，只保留「本身是好数、数位和不是好数」的数字存入数组。

子步骤1：二进制掩码枚举0~9数字子集

用掩码mask遍历1 ~ (1<<10)-1，每一位mask代表数字0-9是否被选用：

• • mask第i位=1：代表数字i参与构造数字；

• • 每个非空mask对应唯一一组不重复数字，能构造一个严格递减数、一个严格递增数。

从9到0遍历数字，mask选中则拼接在数字末尾：
示例mask含1、0：拼接顺序9→1→0，得到10，严格递减；
拼接同时累加所有选中数字得到数位和sum；
拼接完成后判断：若sum不是好数（!isGood(sum)），把这个递减数字存入goodNums。

子步骤3：构造严格递增好数，做前置合法性校验

严格递增数字不能以0开头：若mask包含数字0（mask最低位为1），直接跳过本轮递增数构造；
从1到9从小到大遍历选中数字，依次拼接，生成严格递增数字，同步计算数位和sum；
若sum不是好数，存入goodNums数组。

子步骤4：全局数组排序

全部mask遍历完成后，对goodNums升序排序。排序目的是使用二分查找快速统计区间数字个数。

步骤2：二分查找统计区间[l,r]内模块A数字数量

sort.SearchInts二分查找：

1. 1. 查找第一个 ≥ l 的下标leftIdx；

2. 2. 查找第一个 ≥ r+1 的下标rightIdx；

3. 3. 区间内数量 = rightIdx - leftIdx，记为ans。

   模块A统计的是：区间内「本身是好数，且数位和不是好数」的数字。 后续模块B会统计所有「数位和是好数」的数字（包含那些本身是好数的重叠数字），两者相加刚好覆盖全部奇妙数。

输入范围极大（最高1e15，15位数字），无法暴力枚举，使用数字数位DP求解，统计满足「数位和s是好数」的所有数字，不限制数字本身是否为好数。

前置预处理步骤

1. 1. 将左右边界l、r转为字符串lowS、highS，获取高位数长度n（取r的位数，统一补前导空位对齐两个数字长度）；

2. 2. 计算长度差值diffLH = r的位数 - l的位数，用于处理l位数更少时的前导空白位；

3. 3. 初始化DP记忆数组memo：memo[i][sum]，i为当前处理到第几位，sum为当前累计数位和；

• • 最大位数15，每位最大9，数位和上限15*9=135；

• • 记忆数组存储无上下界约束时，后续合法数字总数；采用标记res+1区分未访问状态，无需初始化为-1。

当前数字构造完成，判断累计数位和digitSum是否为好数：

• • 是好数：返回1（该数字合法，计入统计）；

• • 不是好数：返回0。

若当前数字不受下界、上界任何约束（limitLow=false && limitHigh=false）：

• • 检查memo[i][digitSum]是否存在缓存结果；

• • 存在则直接读取缓存值减1返回；

• • 不存在则递归计算结果，执行defer延迟存入缓存（存res+1区分未访问）。

• • lo：下界约束，若当前位落在l有效数字区间内，lo取lowS对应位数字，否则lo=0；

• • hi：上界约束，若开启上界紧约束，hi取highS对应位数字，否则hi=9。

当l位数小于r位数（i < diffLH）且开启下界约束：

• • 当前位可以不填数字（前导空白，不计入数位和），递归下一位，limitLow保持true、limitHigh改为false；

• • 后续填充数字从d=1开始（数字不能前导0）。

从d初始值循环到hi，每选一个数字：

• • 新数位和 = digitSum + d；

• • 更新新约束：仅当当前d等于边界值时，对应约束保持true，否则释放约束；

• • 递归下一位，返回值累加至总结果res。

调用dfs(0,0,true,true)，得到[l,r]内所有数位和为好数的数字总数。

二、总结果合并逻辑

奇妙数 = A类数字（本身是好数、数位和非好数） + B类数字（数位和是好数，不限是否好数）
两类相加无重复漏算：

• • 数字本身是好数且数位和是好数：仅在B类统计一次；

• • 数字本身是好数、数位和不是好数：仅在A类统计一次；

• • 数字本身不是好数、数位和是好数：仅在B类统计一次；
  全部三类合并刚好覆盖所有奇妙数。

1. 1. 模块A：goodNums存储「本身是好数、数位和不是好数」，8、9、10都是好数，分别计算数位和：

• • 8：和=8，是个位数，两位不等判定为好数 → 不存入goodNums；

• • 9：和=9，是好数 → 不存入goodNums；

• • 10：和=1，是好数 → 不存入goodNums；
  二分查找区间[8,10]，A结果ans=0。

2. 模块B：统计数位和为好数的数字：

• • 8：和8是好数，计数+1；

• • 9：和9是好数，计数+1；

• • 10：和1是好数，计数+1；
  DFS返回3。

3. 总和0+3=3，与题目输出一致。

三、时间复杂度、额外空间复杂度分析 1. 预处理阶段（init函数，仅程序启动运行1次，不计入单次查询耗时） 时间

掩码循环：2^10=1024次循环，每次循环构造两个数字，最多遍历10位数字，总固定常数1024210=20480次运算，O(1)常数复杂度。

空间

goodNums数组固定仅139个元素，常数空间O(1)。

2. 单次查询 countFancy(l,r) 时间复杂度 （1）二分统计模块A

二分查找长度139的数组，二分次数log₂139≈8次，O(1)常数。

（2）数位DP核心耗时

设最大位数 len=15（1e15最多15位），数位和最大sum_max=15*9=135；
状态总数 = 位数 × 数位和 × limitLow(2种) × limitHigh(2种)
= 15 × 135 × 2 × 2 = 8100 个状态；
每个状态仅遍历0~9共10个数字分支，总运算量固定为常数级。
单次查询整体时间复杂度：O(1)（常数，与l、r数值无关）。

3. 单次查询额外空间复杂度

1. 1. DP记忆数组memo：15 × 136 = 2040 个int64，固定常数；

2. 2. DFS递归栈深度最大15层；

3. 3. 存储数字字符串lowS、highS长度最多15；
   单次查询额外空间：O(1)常数空间。

1. 1. 整体时间复杂度（单次查询）：O(1)，所有循环、状态、预处理均为固定常数，不受输入l、r大小影响；

2. 2. 整体额外空间复杂度：O(1)，全局数组与单次DP内存均为固定常量，无随输入扩张的存储空间。

package main

 import (
    "fmt"
    "slices"
    "sort"
    "strconv"
)

 // 数位和不是好数的好数（只有 139 个）
var goodNums []int

 func init() {
    // 枚举 {0,1,2,...,9} 的非空子集
    for mask := 1; mask < 1<<10; mask++ {
        // 构造严格递减好数
        x := 0
        sum := 0
        for i := 9; i >= 0; i-- { // 从大到小遍历子集中的元素
            if mask>>i&1 > 0 {
                x = x*10 + i
                sum += i
            }
        }
        if !isGood(sum) {
            goodNums = append(goodNums, x)
        }

         // 构造严格递增好数
        if mask&1 > 0 { // 不能包含 0
            continue
        }
        x = 0
        sum = 0
        for i := 1; i < 10; i++ { // 从小到大遍历子集中的元素
            if mask>>i&1 > 0 {
                x = x*10 + i
                sum += i
            }
        }
        if !isGood(sum) {
            goodNums = append(goodNums, x)
        }
    }

     slices.Sort(goodNums) // 方便二分求个数
}

 // 判断数位和 s 是否为好数
func isGood(s int)bool {
    if s < 100 { // s 是个位数或者两位数
        return s/10 != s%10// 十位和个位不相等即为好数
    }
    // s 是三位数，其百位一定是 1
    return1 < s/10%10 && s/10%10 < s%10// 只能严格递增
}

 func countFancy(l, r int64)int64 {
    // 计算 [l, r] 内的数位和不是好数的好数的个数
    ans := int64(sort.SearchInts(goodNums, int(r+1)) - sort.SearchInts(goodNums, int(l)))

     // 计算 [l, r] 内的数位和是好数的数的个数（这个数是不是好数都可以）
    lowS := strconv.FormatInt(l, 10)
    highS := strconv.FormatInt(r, 10)
    n := len(highS)
    diffLH := n - len(lowS)
    memo := make([][]int64, n)
    for i := range memo {
        memo[i] = make([]int64, n*9+1) // 数位和最大 9n
    }

     var dfs func(int, int, bool, bool)int64
    dfs = func(i, digitSum int, limitLow, limitHigh bool) (res int64) {
        if i == n {
            if isGood(digitSum) {
                return1// 合法
            }
            return0// 不合法
        }
        if !limitLow && !limitHigh {
            dv := &memo[i][digitSum]
            if *dv > 0 {
                return *dv - 1
            }
            deferfunc() { *dv = res + 1 }() // 这样写无需初始化 memo 为 -1
        }

         lo := 0
        if limitLow && i >= diffLH {
            lo = int(lowS[i-diffLH] - '0')
        }
        hi := 9
        if limitHigh {
            hi = int(highS[i] - '0')
        }

         d := lo
        // 通过 limitLow 和 i 可以判断能否不填数字，无需 isNum 参数
        if limitLow && i < diffLH {
            // 不填数字，上界不受约束
            res = dfs(i+1, 0, true, false)
            d = 1// 下面填数字，从 1 开始填
        }

         for ; d <= hi; d++ {
            res += dfs(i+1, digitSum+d, limitLow && d == lo, limitHigh && d == hi)
        }
        return
    }

     return ans + dfs(0, 0, true, true)
}

 func main() {
    l := 8
    r := 10
    result := countFancy(int64(l), int64(r))
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

 import bisect

 def is_good(s: int) -> bool:
    """判断数位和 s 是否为好数"""
    if s < 100:
        # 个位数或两位数：十位和个位不相等
        return (s // 10) != (s % 10)
    # s 是三位数（实际不会发生，但保留逻辑）
    return1 < (s // 10 % 10) < (s % 10)

 # 预处理所有“数位和不是好数”的好数（仅有 139 个）
good_nums = []

 for mask in range(1, 1 << 10):
    # 构造严格递减好数（从高到低取数字）
    x = 0
    digit_sum = 0
    for i in range(9, -1, -1):
        if mask & (1 << i):
            x = x * 10 + i
            digit_sum += i
    if not is_good(digit_sum):
        good_nums.append(x)

     # 构造严格递增好数（从低到高取数字，不含 0）
    if mask & 1:          # 子集包含 0，则跳过
        continue
    x = 0
    digit_sum = 0
    for i in range(1, 10):
        if mask & (1 << i):
            x = x * 10 + i
            digit_sum += i
    if not is_good(digit_sum):
        good_nums.append(x)

 good_nums.sort()

 def count_fancy(l: int, r: int) -> int:
    """
    计算 [l, r] 内满足条件的数的个数：
      1) 本身是好数（数位严格递增或递减）且数位和不是好数
      2) 或者数位和是好数（不要求本身是好数）
    """
    # 区间内 good_nums 的个数
    ans = bisect.bisect_left(good_nums, r + 1) - bisect.bisect_left(good_nums, l)

     low_s = str(l)
    high_s = str(r)
    n = len(high_s)
    diff = n - len(low_s)

     max_sum = 9 * n
    memo = [[-1] * (max_sum + 1) for _ in range(n)]

     def dfs(i: int, digit_sum: int, limit_low: bool, limit_high: bool) -> int:
        if i == n:
            return1if is_good(digit_sum) else0

         if not limit_low and not limit_high:
            if memo[i][digit_sum] != -1:
                return memo[i][digit_sum]

         lo = 0
        if limit_low and i >= diff:
            lo = int(low_s[i - diff])

         hi = 9
        if limit_high:
            hi = int(high_s[i])

         res = 0
        d = lo

         # 处理低边界位数不足的情况：允许跳过当前位（相当于填 0）
        if limit_low and i < diff:
            res = dfs(i + 1, 0, True, False)   # 不填数字，上界约束解除
            d = 1                              # 若填数字，不能填 0（避免重复）

         while d <= hi:
            res += dfs(
                i + 1,
                digit_sum + d,
                limit_low and d == lo,
                limit_high and d == hi
            )
            d += 1

         if not limit_low and not limit_high:
            memo[i][digit_sum] = res

         return res

     return ans + dfs(0, 0, True, True)

 if __name__ == "__main__":
    l, r = 8, 10
    print(count_fancy(l, r))

C++完整代码如下：

  

using namespace std;

 // 判断数位和 s 是否为好数
bool isGood(int s) {
    if (s < 100) {
        // 个位数或两位数：十位和个位不相等
        return (s / 10) != (s % 10);
    }
    // s 是三位数，其百位一定是1
    return1 < (s / 10 % 10) && (s / 10 % 10) < (s % 10);
}

 // 预处理所有"数位和不是好数"的好数（仅有139个）
vector goodNums;

 void init() {
    // 枚举 {0,1,2,...,9} 的非空子集
    for (int mask = 1; mask < (1 << 10); mask++) {
        // 构造严格递减好数
        int x = 0;
        int sum = 0;
        for (int i = 9; i >= 0; i--) {
            if (mask & (1 << i)) {
                x = x * 10 + i;
                sum += i;
            }
        }
        if (!isGood(sum)) {
            goodNums.push_back(x);
        }

         // 构造严格递增好数
        if (mask & 1) {  // 不能包含0
            continue;
        }
        x = 0;
        sum = 0;
        for (int i = 1; i < 10; i++) {
            if (mask & (1 << i)) {
                x = x * 10 + i;
                sum += i;
            }
        }
        if (!isGood(sum)) {
            goodNums.push_back(x);
        }
    }

     sort(goodNums.begin(), goodNums.end());
}

 long long countFancy(long long l, long long r) {
    // 计算 [l, r] 内的数位和不是好数的好数的个数
    long long ans = upper_bound(goodNums.begin(), goodNums.end(), r) -
                    lower_bound(goodNums.begin(), goodNums.end(), l);

     // 计算 [l, r] 内的数位和是好数的数的个数（这个数是不是好数都可以）
    string lowS = to_string(l);
    string highS = to_string(r);
    int n = highS.length();
    int diffLH = n - lowS.length();

     // memo[i][digitSum] 表示从第i位开始，当前数位和为digitSum时的方案数
    // 使用 -1 表示未计算
    vector 
 
 > memo(n, vector 
 
 (n *  
 
 9 + 1, -1));

     function 
 
 int 
 ,  
 int 
 ,  
 bool 
 ,  
 bool 
 )> dfs = [&]( 
 int 
  i,  
 int 
  digitSum,  
 bool 
  limitLow,  
 bool 
  limitHigh) -> long long { 
 
 
          
 if 
  (i == n) { 
 
 
              
 return 
  isGood(digitSum) ?  
 1 
  :  
 0 
 ; 
 
 
         } 
 
 
 
 
          
 if 
  (!limitLow && !limitHigh) { 
 
 
              
 if 
  (memo[i][digitSum] !=  
 -1 
 ) { 
 
 
                  
 return 
  memo[i][digitSum]; 
 
 
             } 
 
 
         } 
 
 
 
 
          
 int 
  lo =  
 0 
 ; 
 
 
          
 if 
  (limitLow && i >= diffLH) { 
 
 
             lo = lowS[i - diffLH] -  
 '0' 
 ; 
 
 
         } 
 
 
          
 int 
  hi =  
 9 
 ; 
 
 
          
 if 
  (limitHigh) { 
 
 
             hi = highS[i] -  
 '0' 
 ; 
 
 
         } 
 
 
 
 
         long long res =  
 0 
 ; 
 
 
          
 int 
  d = lo; 
 
 
 
 
          
 // 通过 limitLow 和 i 可以判断能否不填数字 
 
 
          
 if 
  (limitLow && i < diffLH) { 
 
 
              
 // 不填数字，上界不受约束 
 
 
             res = dfs(i +  
 1 
 ,  
 0 
 ,  
 true 
 ,  
 false 
 ); 
 
 
             d =  
 1 
 ;   
 // 下面填数字，从1开始填 
 
 
         } 
 
 
 
 
          
 for 
  (; d <= hi; d++) { 
 
 
             res += dfs(i +  
 1 
 , digitSum + d, 
 
 
                        limitLow && (d == lo), 
 
 
                        limitHigh && (d == hi)); 
 
 
         } 
 
 
 
 
          
 if 
  (!limitLow && !limitHigh) { 
 
 
             memo[i][digitSum] = res; 
 
 
         } 
 
 
 
 
          
 return 
  res; 
 
 
     }; 
 
 
 
 
      
 return 
  ans + dfs( 
 0 
 ,  
 0 
 ,  
 true 
 ,  
 true 
 ); 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     init(); 
 
 
 
 
     long long l =  
 8 
 , r =  
 10 
 ; 
 
 
     long long result = countFancy(l, r); 
 
 
     cout << result << endl; 
 
 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。