P2840. 恢复数字序列

解题思路

直接从序列 s 中进行判断，较难完成。 考虑到数据量不大，可以通过穷举的方式来完成。

对于 1 到 1000 的数字 num，考虑长度为 n 的序列：

将该序列中的每一个数字转化为字符串，再统计每一个数字字符出现的个数，用哈希表 cnt_new 来记录。 原序列 s 中的数字字符，用另外一个哈希表 cnt 来记录。即：

或者更加简洁的写法：

若发现存在 cnt_new == cnt，说明此时 num 是所寻找的序列的第一个数字。

这是一种相对而言比较暴力的解法，但也足以通过所有用例。

如果想要进一步优化，可以使用固定滑窗的做法。 固定长度为序列长度 n 的窗口，对正整数序列 1 2 3 ... 1000 进行滑动，构建一个 win_cnt 表示窗口中各个数字出现的次数。 左边的数字离开，则在 win_cnt 中减去对应的频次；右边的数字加入，则在 win_cnt 中加入对应的频次。

感兴趣的同学可以自行完成上述代码。

复杂度分析 设 n 为序列长度（输入的第二个数），候选起始数的枚举上界为 1000，d 为单个数字的位数（不超过 4）。

• 时间复杂度：O(1000 × n × d)。瓶颈在外层 for 循环：对 1 到 1000 的每个候选起始数 num，都要把 num 到 num+n-1 这 n 个数转成字符串拼接，并用 Counter 统计一遍，单轮代价约为 n × d；两个计数器的相等比较只涉及 '0' 到 '9' 十种键，是常数代价。
• 空间复杂度：O(n × d)。主要开销是每轮拼接出来的临时字符串；计数器 cnt 与 cnt_new 至多各含 10 个键，属于常数空间。

边界与注意事项

• 匹配的判断依据是「数字字符的出现次数是否完全一致」，与字符顺序无关，所以题面中字符被打乱不影响判断。
• 枚举从 1 开始递增，第一个使 cnt_new == cnt 成立的 num 即被输出并 break，天然满足题面「输出序列中最小的那个数字」的要求。
• 代码把候选起始数的范围定为 1 到 1000，这是实现的前提假设；若起始数超出该范围，循环会空跑结束且没有输出。
• n = 1 时序列只含一个数，两个计数器的比较同样成立，无需特判。
• 输入是一行内以空格分隔的字符串 s 和序列长度 n，n 必须先转成整数再参与区间计算。