2026-03-02：统计和为 N 的无零数对。用go语言，把十进制表示中不含数字 0 的正整数称为“不含零的正数”。给定一个整数 n，统计所有满足

福大大架构师每日一题

发布于 2026-03-04 19:55:09

1030

2026-03-02：统计和为 N 的无零数对。用go语言，把十进制表示中不含数字 0 的正整数称为“不含零的正数”。给定一个整数 n，统计所有满足下述条件的整数对 (a, b) 的数量：a 和 b 都是不含零的正数，且 a + b = n。返回这些符合条件的配对总数。

2 <= n <= 1000000000000000。

输入: n = 11。

输出: 8。

解释:

数对有 (2, 9)、(3, 8)、(4, 7)、(5, 6)、(6, 5)、(7, 4)、(8, 3) 和 (9, 2)。请注意，(1, 10) 和 (10, 1) 不满足条件，因为 10 在其十进制表示中包含 0。

题目来自力扣3704。

一、代码执行的核心逻辑与分步过程（以 n=11 为例）

我们先明确核心目标：统计所有满足 a + b = 11、且 a/b 均为「无零正数」（十进制不含0）的数对 (a,b) 数量。代码采用数位DP（动态规划）+ 记忆化搜索 的思路，从数位层面逐位验证数对的合法性，以下拆解详细过程：

步骤1：初始化与前置处理

• 输入 n=11 先转为字符串 s="11"，长度 m=2（表示n是两位数）。
• 定义记忆化数组 memo：维度为 [m][2][2]，其中：
- • 第一维 i：当前处理的数位下标（从高位到低位，本例中是下标1→0，对应数字1→1）；
- • 第二维 borrowed：标记是否向高位借位（0=无借位，1=有借位）；
- • 第三维 isNum：标记数对是否已脱离「前导零」状态（0=仍有前导零，1=无零且是有效数）；
- • 初始值 -1 表示该状态未计算过，避免重复递归。

步骤2：核心DFS递归函数的逻辑框架

DFS函数 dfs(i, borrowed, isNum) 的作用是：从第 i 位开始，在「是否借位 borrowed」「是否有效数 isNum」的状态下，统计符合条件的数对数量。递归的终止条件是 i < 0（所有数位处理完毕），此时仅当 borrowed=0（无未偿还的借位）时，才算1个有效方案。

步骤3：以 n=11 为例的递归执行过程（从高位到低位处理）

n=11 的数位拆解：高位（i=1）是数字1，低位（i=0）是数字1。递归从 dfs(1, 0, 1) 开始（处理第1位，无借位，初始为有效数状态）。

阶段1：处理高位（i=1，当前数位数字 d = 1 - borrowed(0) = 1）

此时 isNum=1（无前置零，数对为有效数），进入「情况一：两个数位都不为0」的逻辑：

• 子情况1.1：不向高位借位（borrowed=0） 需计算 twoSumWays(d=1)：twoSumWays(target) 是核心辅助函数，返回「两个1~9的整数和为target的方案数」。
- • target=1 时，1~9中无两个数相加等于1，因此 twoSumWays(1)=0；
- • 递归调用 dfs(0, 0, 1)，结果乘以0，无贡献。
• 子情况1.2：向高位借位（borrowed=1） 借位后目标和变为 d+10=11，计算 twoSumWays(11)：👉 处理 dfs(0, 1, 1)（低位i=0，有借位borrowed=1，有效数状态）：
- • 当前数位数字 d = 1 - borrowed(1) = 0；
- • isNum=1，进入「情况一」：
  - • 不借位：twoSumWays(d=0)=0，递归 dfs(-1, 0, 1) 无贡献；
  - • 借位：twoSumWays(d+10=10)，但i=0是最低位，借位后无更高位可借，dfs(-1, 1, 1) 返回0（终止条件要求borrowed=0）；
- • 「情况二」（前导零）：i=0是最低位，不触发；
- • 最终 dfs(0, 1, 1) 返回0？❌ 修正：实际递归逻辑中，twoSumWays(11)=8 是直接统计的「数位和为11且无零」的组合数，而低位处理仅验证借位是否合法——本例中高位借位后，低位无需再借位，因此 dfs(0, 1, 1) 实际返回1（借位偿还完毕），最终这部分贡献为 8 * 1 = 8。
- • 1~9中两数和为11的组合有：(2,9)、(3,8)、(4,7)、(5,6)、(6,5)、(7,4)、(8,3)、(9,2)，共8种，因此 twoSumWays(11)=8；
- • 递归调用 dfs(0, 1, 1)，需计算该递归的返回值。
• 情况二：前导零处理 i=1 不是最低位，但 d=1≠0，需计算「其中一个数位填前导零」的情况：
- • isNeg(d=1)=0（d非负，无需借位），递归 dfs(0, 0, 0)，并乘以 isNum+1=2；
- • 但 dfs(0, 0, 0) 处理低位时，因前导零状态下的数对（如a=01=1，b=10，含0）会被过滤，最终这部分贡献为0。

阶段2：递归终止与结果汇总

所有递归分支处理完毕后，dfs(1, 0, 1) 最终返回8，与题目预期输出一致（对应数对：(2,9)、(3,8)、(4,7)、(5,6)、(6,5)、(7,4)、(8,3)、(9,2)）。

步骤4：关键辅助函数的作用

• twoSumWays(target)：快速计算「两个1~9的数和为target」的方案数，公式 max(min(target-1, 19-target), 0) 的逻辑：
- • 两数和为target，且均∈[1,9] → 第一个数的取值范围是 max(1, target-9) 到 min(9, target-1)；
- • 例如target=11时，取值范围是2~9，共8个值，对应8种方案；
- • 若target<2或target>18，返回0（无合法组合）。
• isNeg(d)：标记当前数位计算结果是否为负（负则需向高位借位）。

二、时间复杂度与空间复杂度分析

1. 时间复杂度：O(log n)

• 核心是数位DP的递归过程，递归的状态数由「数位长度」和「状态维度」决定：
- • 数位长度：n的十进制位数为 log₁₀n（例如n=1e15时，数位长度为15）；
- • 状态维度：borrowed 有2种状态（0/1），isNum 有2种状态（0/1）；
- • 总状态数 = 数位长度 × 2 × 2 = O(4×log n) = O(log n)；
- • 每个状态仅计算1次（记忆化避免重复），单个状态的计算是O(1)（仅调用twoSumWays等简单函数）；
• 因此总时间复杂度为 O(log n)（n为输入的数值大小）。

2. 额外空间复杂度：O(log n)

• 主要额外空间来自：
- • 记忆化数组 memo：空间大小 = 数位长度 × 2 × 2 = O(log n)；
- • 递归调用栈：深度等于数位长度，即O(log n)；
• 其他临时变量（如字符串s、辅助函数的局部变量）的空间可忽略；
• 因此总额外空间复杂度为 O(log n)。

总结

1. 核心过程：将「统计a+b=n且a/b无零的数对」转化为「数位层面验证两数之和的每一位合法性」，通过DFS+记忆化枚举数位状态，结合twoSumWays快速计算单个数位的合法组合数，最终汇总所有有效方案；
2. 时间复杂度：O(log n)（仅与n的十进制位数相关，与n的数值大小无关）；
3. 空间复杂度：O(log n)（记忆化数组和递归栈的空间均由数位长度决定）。

Go完整代码如下：

package main

import (
    "fmt"
    "strconv"
)

// 返回两个 1~9 的整数和为 target 的方案数
func twoSumWays(target int)int {
    return max(min(target-1, 19-target), 0) // 保证结果非负
}

func countNoZeroPairs(n int64)int64 {
    s := strconv.FormatInt(n, 10)
    m := len(s)
    memo := make([][2][2]int, m)
    for i := range memo {
        memo[i] = [2][2]int{{-1, -1}, {-1, -1}} // -1 表示没有计算过
    }

    // borrowed = 1 表示被低位（i+1）借了个 1
    // isNum = 1 表示之前填的数位，两个数都无前导零
    var dfs func(int, int, int)int
    dfs = func(i, borrowed, isNum int) (res int) {
        if i < 0 {
            // borrowed 必须为 0
            return borrowed ^ 1
        }

        p := &memo[i][borrowed][isNum]
        if *p >= 0 { // 之前计算过
            return *p
        }
        deferfunc() { *p = res }() // 记忆化

        d := int(s[i]-'0') - borrowed

        // 情况一：两个数位都不为 0
        if isNum > 0 {
            res = dfs(i-1, 0, 1) * twoSumWays(d)     // 不向高位借 1
            res += dfs(i-1, 1, 1) * twoSumWays(d+10) // 向高位借 1
        }

        // 情况二：其中一个数位填前导零
        if i < m-1 { // 不能是最低位
            if d != 0 {
                // 如果 d < 0，必须向高位借 1
                // 如果 isNum = 1，根据对称性，方案数要乘以 2
                res += dfs(i-1, isNeg(d), 0) * (isNum + 1)
            } elseif i == 0 { // 两个数位都填 0，只有当 i = 0 的时候才有解
                res++
            }
        }
        return
    }

    returnint64(dfs(m-1, 0, 1))
}

// 返回 d 是否为负数
func isNeg(d int)int {
    if d < 0 {
        return1
    }
    return0
}

func main() {
    n := int64(11)
    result := countNoZeroPairs(n)
    fmt.Println(result)
}

Python完整代码如下：

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

def two_sum_ways(target: int) -> int:
    """返回两个 1~9 的整数和为 target 的方案数"""
    return max(min(target - 1, 19 - target), 0)  # 保证结果非负

def is_neg(d: int) -> int:
    """返回 d 是否为负数"""
    return1if d < 0else0

def count_no_zero_pairs(n: int) -> int:
    s = str(n)
    m = len(s)
    
    # 记忆化数组 memo[i][borrowed][isNum]
    # borrowed = 1 表示被低位（i+1）借了个 1
    # isNum = 1 表示之前填的数位，两个数都无前导零
    memo = [[[-1, -1] for _ in range(2)] for _ in range(m)]
    
    def dfs(i: int, borrowed: int, isNum: int) -> int:
        """深度优先搜索"""
        if i < 0:
            # borrowed 必须为 0
            return borrowed ^ 1
        
        if memo[i][borrowed][isNum] >= 0:  # 之前计算过
            return memo[i][borrowed][isNum]
        
        d = int(s[i]) - borrowed
        
        res = 0
        
        # 情况一：两个数位都不为 0
        if isNum > 0:
            res = dfs(i - 1, 0, 1) * two_sum_ways(d)      # 不向高位借 1
            res += dfs(i - 1, 1, 1) * two_sum_ways(d + 10) # 向高位借 1
        
        # 情况二：其中一个数位填前导零
        if i < m - 1:  # 不能是最低位
            if d != 0:
                # 如果 d < 0，必须向高位借 1
                # 如果 isNum = 1，根据对称性，方案数要乘以 2
                res += dfs(i - 1, is_neg(d), 0) * (isNum + 1)
            elif i == 0:  # 两个数位都填 0，只有当 i = 0 的时候才有解
                res += 1
        
        memo[i][borrowed][isNum] = res
        return res
    
    return dfs(m - 1, 0, 1)

def main():
    n = 11
    result = count_no_zero_pairs(n)
    print(result)

if __name__ == "__main__":
    main()

C++完整代码如下：

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

using namespace std;

// 返回两个 1~9 的整数和为 target 的方案数
int twoSumWays(int target) {
    return max(min(target - 1, 19 - target), 0); // 保证结果非负
}

// 判断 d 是否为负数
int isNeg(int d) {
    return d < 0 ? 1 : 0;
}

// 记忆化数组
vector<vector<vector<int>>> memo;

// DFS 函数
int dfs(int i, int borrowed, int isNum, conststring& s) {
    if (i < 0) {
        // borrowed 必须为 0
        return borrowed ^ 1;
    }

    if (memo[i][borrowed][isNum] >= 0) {
        return memo[i][borrowed][isNum];
    }

    int res = 0;
    int d = (s[i] - '0') - borrowed;

    // 情况一：两个数位都不为 0
    if (isNum > 0) {
        res = dfs(i - 1, 0, 1, s) * twoSumWays(d);     // 不向高位借 1
        res += dfs(i - 1, 1, 1, s) * twoSumWays(d + 10); // 向高位借 1
    }

    // 情况二：其中一个数位填前导零
    if (i < (int)s.length() - 1) { // 不能是最低位
        if (d != 0) {
            // 如果 d < 0，必须向高位借 1
            // 如果 isNum = 1，根据对称性，方案数要乘以 2
            res += dfs(i - 1, isNeg(d), 0, s) * (isNum + 1);
        } elseif (i == 0) { // 两个数位都填 0，只有当 i = 0 的时候才有解
            res++;
        }
    }

    memo[i][borrowed][isNum] = res;
    return res;
}

long long countNoZeroPairs(long long n) {
    string s = to_string(n);
    int m = s.length();

    // 初始化记忆化数组
    memo.assign(m, vector<vector<int>>(2, vector<int>(2, -1)));

    return dfs(m - 1, 0, 1, s);
}

int main() {
    long long n = 11;
    long long result = countNoZeroPairs(n);
    cout << result << endl;
    return0;
}