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 {
		return 0
	}

	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 { // 不合法
				return 0
			}
			return 1
		}
		if !limitLow && !limitHigh {
			p := &memo[i][diff+n/2*9] // 保证下标非负
			if *p > 0 {
				return *p - 1
			}
			defer func() { *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:
        return 0

    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:
            return 1 if diff == 0 else 0

        # 记忆化：只有当不受 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 = 1 if i % 2 == 0 else -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++完整代码如下：

#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <algorithm>
#include <cstring>

using namespace std;

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

    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<vector<long long>> memo(n, vector<long long>(n * 9 + 1, -1));

    // 使用函数对象实现递归
    function<long long(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;
}