2026-05-07：给定范围内平衡整数的数目。用go语言，给定两个整数 low 和 high，统计在闭区间 [low, high] 内满足“平衡”条件…

2026-05-07：给定范围内平衡整数的数目。用go语言，给定两个整数 low 和 high，统计在闭区间 [low, high] 内满足“平衡”条件的整数个数。

对某个整数，先要求它至少是两位数。接着把它的每一位数字按位置从左到右编号，最左边是第 1 位。将所有在奇数位上的数字相加，得到奇数位数字和；再把所有在偶数位上的数字相加，得到偶数位数字和。如果这两个和相等，则该整数被称为“平衡整数”。

最终，你需要返回区间 [low, high] 中所有平衡整数的数量。

1 <= low <= high <= 1000000000000000。

输入： low = 1, high = 100。

输出： 9。

解释：

1 到 100 之间共有 9 个平衡数，分别是 11、22、33、44、55、66、77、88 和 99。

题目来自力扣3791。

平衡整数计数代码执行过程分步详解 一、代码整体执行步骤（分阶段） 阶段1：基础边界过滤

1. 函数接收low和high两个超大整数（int64类型）；

2. 首先判断：如果high < 11，直接返回0（因为最小的平衡数是11，没有符合条件的数）；

3. 把low修正为max(low, 11)，排除1-10这些无效数字，缩小计算范围。

阶段2：数字格式化与预处理

1. 将修正后的low和high转换成字符串：

• 目的：方便逐位处理每一位数字（数位DP的核心操作）；

2. 计算high的字符串长度n（最大数字的位数）：

• 示例中high=100，字符串是"100"，长度n=3；

3. 计算diffLH：high的位数 –low的位数，用于后续限制低位数字的枚举范围；

4.初始化记忆化数组（memo）：

• 二维数组：第一维是当前处理到第几位（0~n-1），第二维是奇偶位差值的存储位；

• 作用：缓存已经计算过的状态，避免重复递归，大幅提升效率。

阶段3：核心逻辑 —— 数位DFS递归（深度优先搜索）

定义递归函数dfs，这是数位DP的核心，参数含义：

•i：当前正在处理第i位数字（从0开始，对应数字的最高位）；

•diff：奇数位和 – 偶数位和的差值（最终diff=0就是平衡数）；

•limitLow：布尔值，当前位是否受low的下限约束；

•limitHigh：布尔值，当前位是否受high的上限约束。

递归执行流程：

子步骤1：递归终止条件

当i == n（所有位数处理完毕）：

• 判断diff是否等于0：

• 等于0 → 是平衡数，返回1（计数+1）；

• 不等于0 → 不是平衡数，返回0。

子步骤2：记忆化缓存读取

如果当前不受low和high的数字限制（可以自由枚举0-9）：

1. 计算记忆数组的下标（将差值偏移为非负数，防止数组越界）；

2. 如果该状态已经计算过 → 直接返回缓存的结果，不重复计算；

3. 如果没计算过 → defer延迟存储结果，计算完成后写入缓存。

子步骤3：确定当前位的枚举范围

根据limitLow和limitHigh，限制当前位能选的数字：

• 下限lo：受约束时=low对应位的数字，不受约束时=0；

• 上限hi：受约束时=high对应位的数字，不受约束时=9；

• 示例：处理100的百位时，hi只能是1，不能超过high的数字。

子步骤4：枚举当前位的所有合法数字

循环遍历从lo到hi的每一个数字d：

1.更新差值diff：

• 第i位是奇数位（i%2=0）：diff = diff + d；

• 第i位是偶数位（i%2=1）：diff = diff – d；

2.更新约束条件：

• 下一位的limitLow= 当前约束 且 当前选的数字=下限；

• 下一位的limitHigh= 当前约束 且 当前选的数字=上限；

3. 递归调用下一位，累加所有合法结果。

子步骤5：返回累计结果

将当前位所有枚举情况的结果求和，返回给上一层递归。

阶段4：返回最终答案

启动递归dfs(0, 0, true, true)（从第0位开始，初始差值为0，同时受low和high约束），函数返回的就是[low, high]内平衡整数的总数量。

二、针对示例输入的执行验证

输入：low=1，high=100

1. 过滤：high=100≥11，low修正为11；

2. 格式化：low=”11″（2位），high=”100″（3位），n=3；

3. 递归枚举所有11~100的两位数、三位数：

• 两位数（11~99）：奇数位=十位，偶数位=个位，十位=个位 → 11、22…99，共9个；

• 三位数（100）：奇数位（百位+个位）=1+0=1，偶数位（十位）=0，1≠0 → 不合法；

4. 最终结果=9，与题目输出一致。

三、时间复杂度 & 额外空间复杂度 1. 时间复杂度

O(位数 × 最大差值 × 10)

• 核心变量：

1. 数字最大位数n：10¹⁵对应15位；

2. 奇偶位最大差值：每位最大9，总差值≤15×9=135；

3. 每位枚举数字：0~9共10种选择；

• 总计算量：15 × 135 × 10 =20250（常数级极小计算量）；

• 本质：O(1) 常数时间复杂度（因为位数固定最大15，无变量级增长）。

2. 额外空间复杂度

O(位数 × 最大差值)

• 核心占用：记忆化数组memo；

• 大小：15（位数） × 135（最大差值）=2025个int64元素；

• 递归栈空间：最大深度=数字位数=15，可忽略；

• 本质：O(1) 常数空间复杂度。

总结

1. 代码核心是数位DP+记忆化递归，专门解决超大范围数字的数位统计问题；

2. 执行流程：边界过滤→数字格式化→记忆化DFS逐位枚举→统计合法平衡数；

3. 时间复杂度：O(1)（常数级）；

4. 额外空间复杂度：O(1)（常数级）。

Go完整代码如下：

package main

 import (
    "fmt"
    "strconv"
)

 func countBalanced(low, high int64)int64 {
    // 最小的满足要求的数是 11
    if high < 11 {
        return0
    }

     low = max(low, 11)
    lowS := strconv.FormatInt(low, 10)
    highS := strconv.FormatInt(high, 10)
    n := len(highS)
    diffLH := n - len(lowS)
    memo := make([][]int64, n)
    for i := range memo {
        // diff 至少 floor(n/2) * 9，至多 ceil(n/2) * 9，值域大小 n * 9
        memo[i] = make([]int64, n*9+1)
    }

     var dfs func(int, int, bool, bool)int64
    dfs = func(i, diff int, limitLow, limitHigh bool) (res int64) {
        if i == n {
            if diff != 0 { // 不合法
                return0
            }
            return1
        }
        if !limitLow && !limitHigh {
            p := &memo[i][diff+n/2*9] // 保证下标非负
            if *p > 0 {
                return *p - 1
            }
            deferfunc() { *p = res + 1 }() // 记忆化的时候加一，这样 memo 可以初始化成 0
        }

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

         for d := lo; d <= hi; d++ {
            // 下一个位置奇偶性翻转
            res += dfs(i+1, diff+(1-i%2*2)*d,
                limitLow && d == lo, limitHigh && d == hi)
        }
        return
    }
    return dfs(0, 0, true, true)
}

 func main() {
    low := int64(1)
    high := int64(100)
    result := countBalanced(low, high)
    fmt.Println(result)
}

Python完整代码如下：

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

 def count_balanced(low: int, high: int) -> int:
    if high < 11:
        return0

     low = max(low, 11)
    low_str = str(low)
    high_str = str(high)
    n = len(high_str)
    diff_lh = n - len(low_str)

     # 记忆化数组：memo[i][diff_offset]
    # diff 的取值范围：[-max_diff, max_diff]，max_diff = (n // 2 + (n % 2)) * 9
    max_possible_diff = ((n + 1) // 2) * 9
    memo = [[-1] * (2 * max_possible_diff + 1) for _ in range(n)]

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

         # 记忆化：只有当不受 low 和 high 限制时才能复用
        if not limit_low and not limit_high:
            idx = diff + max_possible_diff
            if memo[i][idx] != -1:
                return memo[i][idx]

         lo = 0
        if limit_low and i >= diff_lh:
            lo = int(low_str[i - diff_lh])

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

         total = 0
        for d in range(lo, hi + 1):
            # 根据位置 i 的奇偶性决定 diff 的增减
            # i=0 是最高位（视为偶数位，与 Go 版本一致）
            sign = 1if i % 2 == 0else-1
            total += dfs(i + 1, diff + sign * d,
                         limit_low and d == lo,
                         limit_high and d == hi)

         if not limit_low and not limit_high:
            memo[i][diff + max_possible_diff] = total
        return total

     return dfs(0, 0, True, True)

 if __name__ == "__main__":
    low_val = 1
    high_val = 100
    result = count_balanced(low_val, high_val)
    print(result)

C++完整代码如下：

  

  

  

   


 using namespace std;

 long long countBalanced(long long low, long long high) {
    // 最小的满足要求的数是 11
    if (high < 11) {
        return0;
    }

     low = max(low, 11LL);
    string lowS = to_string(low);
    string highS = to_string(high);
    int n = highS.length();
    int diffLH = n - lowS.length();

     // 初始化记忆化数组，使用 -1 表示未计算
    vector 
 
 > memo(n, vector 
 
 (n *  
 
 9 + 1, -1));

     // 使用函数对象实现递归
    function 
 
 int 
 ,  
 int 
 ,  
 bool 
 ,  
 bool 
 )> dfs = [&]( 
 int 
  i,  
 int 
  diff,  
 bool 
  limitLow,  
 bool 
  limitHigh) -> long long { 
 
 
          
 if 
  (i == n) { 
 
 
              
 return 
  diff ==  
 0 
  ?  
 1 
  :  
 0 
 ; 
 
 
         } 
 
 
 
 
          
 if 
  (!limitLow && !limitHigh) { 
 
 
              
 int 
  idx = diff + n /  
 2 
  *  
 9 
 ; 
 
 
              
 if 
  (idx >=  
 0 
  && idx < n *  
 9 
  +  
 1 
  && memo[i][idx] !=  
 -1 
 ) { 
 
 
                  
 return 
  memo[i][idx]; 
 
 
             } 
 
 
         } 
 
 
 
 
          
 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 
 ; 
 
 
          
 for 
  ( 
 int 
  d = lo; d <= hi; d++) { 
 
 
              
 // 下一个位置奇偶性翻转 
 
 
             res += dfs(i +  
 1 
 , diff + ( 
 1 
  - i %  
 2 
  *  
 2 
 ) * d, 
 
 
                        limitLow && d == lo, limitHigh && d == hi); 
 
 
         } 
 
 
 
 
          
 if 
  (!limitLow && !limitHigh) { 
 
 
              
 int 
  idx = diff + n /  
 2 
  *  
 9 
 ; 
 
 
              
 if 
  (idx >=  
 0 
  && idx < n *  
 9 
  +  
 1 
 ) { 
 
 
                 memo[i][idx] = res; 
 
 
             } 
 
 
         } 
 
 
 
 
          
 return 
  res; 
 
 
     }; 
 
 
 
 
      
 return 
  dfs( 
 0 
 ,  
 0 
 ,  
 true 
 ,  
 true 
 ); 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     long long low =  
 1 
 ; 
 
 
     long long high =  
 100 
 ; 
 
 
     long long result = countBalanced(low, high); 
 
 
     cout << result << endl; 
 
 
      
 return 
 0 
 ; 
 
 
 } 
 
 
 

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