题目描述

Leetcode 3704题要求统计所有满足以下条件的非零数字对(a, b)的数量：

• a + b = N
• a和b的十进制表示中不包含数字0

例如，当N=11时，有效数字对包括(2,9)、(3,8)、(4,7)、(5,6)等，但(10,1)无效，因为10包含数字0。

解题思路

解决该问题的核心在于高效枚举所有可能的数字对(a, b)，并验证它们是否满足条件。关键在于避免暴力枚举所有可能的组合，而是通过数学性质优化搜索范围。

数学性质

• 由于a和b均为正数且不含数字0，a的取值范围为[1, N-1]。
• 对于任意a，只需检查b=N?a是否有效，且b>0。
• 需要确保a和b的十进制表示中不包含数字0。

算法实现

1. 生成有效数字
   预处理所有小于N且不含数字0的数字，存储在哈希表或列表中以便快速查询。可以通过逐位检查数字的每一位是否非零来实现。

2. 枚举与验证
   遍历所有可能的a（1 ≤ a ≤ N/2），计算b=N?a，检查a和b是否均不含数字0。若满足条件，则计数增加1。由于(a,b)和(b,a)视为同一对，只需遍历到N/2即可避免重复。

代码示例（Python）

def count_no_zero_pairs(N):
    def is_valid(num):
        while num > 0:
            digit = num % 10
            if digit == 0:
                return False
            num = num // 10
        return True
    
    count = 0
    for a in range(1, N // 2 + 1):
        b = N - a
        if is_valid(a) and is_valid(b):
            count += 1
    return count

复杂度分析

• 时间复杂度：O(N log N)
  外层循环遍历O(N)次，内层数字检查每次耗时O(log N)（数字的位数）。
• 空间复杂度：O(1)
  仅使用常数空间存储中间变量。

优化思路

对于大规模N（如1e9），可采用数位动态规划（Digit DP）预先计算范围内所有不含0的数字，再通过二分查找快速配对。但实际竞赛中，题目约束通常允许直接枚举。

边界条件

• N=1时无解，返回0。
• 确保a ≤ b以避免重复计数。
• 数字0本身无效，无需特殊处理。

示例验证

以N=11为例：
有效对：(2,9)、(3,8)、(4,7)、(5,6) → 输出4。
无效对：(1,10)因包含0被排除。