美团 · 穷举 · 算法编程题
美团 穷举 N ≤ 999999 时限 1 秒 / 256 MB

题目描述

小团想要编写一个程序，希望可以统计在M和N之间（M<N，且包含M和N）有多少个六位数ABCDEF满足以下要求：
(1) ABCDEF这六个数字均不相同，即A、B、C、D、E和F表示六个不同的数字。
(2) AB+CD=EF。即将这个六位数拆成三个两位数，使得第1个和第2个两位数的和等于第3个两位数。
数据范围： 100000≤ M < N ≤ 999999
进阶：时间复杂度 O(n) ，空间复杂度 O(1)

输入输出

输入描述
单组输入。
输入两个六位正整数M和N（M<N），两者之间用空格隔开。
输出描述
输出在M到N之间（包含M和N）满足要求的六位数的个数。

样例共 1 组

样例 1
输入
100000 110000
输出
0

算法解析依据充分

考点：穷举

数据规模 N ≤ 999999 ｜ 限制 1 秒 / 256MB ｜ 标准输入输出

题目画像

  • 数据规模：M ≤ 999999，N ≤ 999999
  • 复杂度门槛：只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。
  • 源站时限：1 秒（牛客口径，非本题专属门槛）
  • 题目显式声明：复杂度要求 O(n)、O(1)

解题思路

推荐方向：穷举

本题切入点

六位数规模有限，可在 M..N 区间内逐个拆位判断：六位互不相同且 AB+CD=EF。

把候选答案空间全部列出来逐一检验，靠数据范围小来兜底。

思路框架（穷举 通法 · 非本题专属）

  1. 确定枚举什么（下标区间 / 子集 / 数值）。
  2. 用一层或多层循环（或递归）生成所有候选。
  3. 对每个候选判断是否满足题目条件，满足就统计或更新最优值。
  4. 先按数据范围估算枚举量，确认不会超时。

实现要点：多重循环是最直接的写法；枚举组合时可用递归 + 回溯，或用位掩码代表子集。

复杂度：时间 O(候选数 × 单次校验代价) ｜ 空间 O(1)

该范式的通法易错点

  • 没先估复杂度，枚举量超出时限（这是最常见的超时原因）。
  • 去重没做好，同一种方案被多次统计。

对照本题

  • 数据规模 N ≤ 999999，只允许 O(n) 或 O(n log n)，且常数要小（注意读入效率）。

样例

样例 1

  • 输入：100000 110000
  • 输出：0

解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。

本题来源：美团2023校招技术第7场编程题。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容：无需作答，直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理，非官方题解