Meta 三位数各位不同：有限区间扫描与组合对照

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 100≤left≤right≤999，闭区间，百位不能0，十/个位允许0；每对数字都不同，只返回count。

解题路线

1. 扫描left..right，取百位n//100、十位n//10%10、个位n%10，检查三对不等。不能只检查相邻位，121首尾仍重复。
2. 最多900个数，线性扫描已满足要求，不必引入digit DP。“不要超过right²”不代表必须写平方算法。
3. 独立对照枚举0..9三排列，排除首0形成所有合法数再过滤区间；全三位数9×9×8=648。
4. 越界或left>right拒绝，避免把两位数前导0算百位。一般多位输入要另外定义前导零和复杂度。

手动走一遍

[100,105]只有102/103/104/105合法，答案4；[121,121]为0，[123,123]为1，完整[100,999]为648。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def count_distinct_digits(left,right):
    """Inclusive 100<=left<=right<=999, every digit distinct."""
    if not 100<=left<=right<=999:raise ValueError('three-digit bounds')
    answer=0
    for number in range(left,right+1):
        hundreds=number//100;tens=number//10%10;units=number%10
        answer+=hundreds!=tens and hundreds!=units and tens!=units
    return answer

复杂度

O(right−left+1)时间/O(1)状态，固定三位范围上界900；推广多位需按位数计提取成本。输出count不存全部数。

易错点与追问

容易失分的边界

• 漏百位与个位比较会接受121。
• 禁止十/个位0会漏102。

继续深挖

• 大多位范围如何用tight/started/mask的digit DP？
• 输出列表的空间O(count)不能计常数。