问题描述

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

• a + b = N
• a和b的每一位数字都不包含0

例如，当N=11时，有效数字对包括（2,9）、（3,8）、（4,7）、（5,6）、（6,5）、（7,4）、（8,3）、（9,2），共8对。

解决思路

为了高效解决这个问题，需要遍历所有可能的数字对（a, b），并检查两个数字是否都不包含0。关键在于如何快速验证一个数字是否包含0，并避免重复计算。

方法一：暴力枚举与数字验证

遍历所有可能的a值（从1到N-1），计算对应的b = N - a。对于每一对（a, b），检查a和b是否都不包含数字0。

检查数字是否包含0可以通过逐位分解数字实现：

• 将数字逐位分解，检查每一位是否为0。
• 如果任何一位为0，则该数字无效。

时间复杂度为O(N * log N)，其中log N是数字的位数。

方法二：预处理有效数字

预先筛选出1到N-1范围内所有不包含0的数字，存储在集合或列表中。然后遍历这些数字，检查是否存在对应的互补数字b = N - a也在集合中。

预处理的时间复杂度为O(N log N)，查询的时间复杂度为O(K)，其中K是有效数字的数量。

优化技巧

1. 数字验证优化：使用字符串转换快速检查数字是否包含0。例如，将数字转为字符串后检查是否包含字符'0'。
2. 对称性利用：由于（a, b）和（b, a）被视为不同的对，只需遍历a从1到N/2，然后结果乘以2（注意处理N为偶数时的中间情况）。

代码实现

def count_no_zero_pairs(N):
    def is_no_zero(num):
        return '0' not in str(num)
    
    count = 0
    for a in range(1, N):
        b = N - a
        if b > 0 and is_no_zero(a) and is_no_zero(b):
            count += 1
    return count

测试用例

验证代码的正确性：

• N=11：应返回8。
• N=2：应返回1（只有（1,1））。
• N=101：应返回0（因为101-1=100包含0）。

复杂度分析

• 时间复杂度：O(N log N)，因为对每个数字需要进行位数检查。
• 空间复杂度：O(1)，仅使用常数空间。

进一步优化

对于非常大的N（例如1e9），暴力枚举可能不够高效。可以尝试数学方法或动态规划，但需要更深入的分析。