如果这不是这个问题的正确SE站点，请告诉我。
一位朋友分享了他在电话中收到的这个面试问题，我试图自己解决。 我将解释：
给出最多
pin位数字的值作为字符串。如何在此字符串中找到所有重复的 4 位序列？
这部分似乎相当简单。 向哈希表添加 4 个字符序列，一次递增一个字符。 在插入到哈希表之前，检查当前的 4 个字符序列是否已存在。 如果是这样，那么您已经找到了重复项。 将其存储在某个地方，然后重复该过程。 有人告诉我这或多或少是正确的。
我遇到的问题是关于第二个问题：
上限是多少？
n = 10,000,000就是一个例子。
诚然，我的算法背景非常生疏。 我的第一个想法是，上限一定以某种方式与n有关，但我被告知它不是。
我该如何计算？
编辑：
我也愿意接受一种解决方案，该解决方案无视上限与n无关的限制。 两者都是可以接受的。
只有 10，000 个可能的四位数序列（0000 到 9999 ），所以在某些时候你会发现每个序列都被重复了，不需要再处理数字。
如果您假设pi是一个完全统一的随机数生成器，那么处理的每个新数字都会产生一个新序列，并且在大约 20，000 位数字之后，您将发现所有 10，000 个序列的重复项。鉴于pi并不完美，在复制所有序列之前，您可能需要更多的数字，但 100，000 在上限上是一个合理的猜测。
此外，由于只有 10，000 种可能性，因此您实际上并不需要哈希表。您可以简单地使用一个包含 10000 个计数器的数组 （ int count[10000] ），并增加您找到的每个序列的计数。
解决方案的上限是可以放入内存的哈希表的大小。
另一种技术是生成所有序列并对其进行排序。然后重复项将是相邻的并且易于检测。与哈希表相比，您通常可以更多地适应线性数据结构，并且如果您仍然耗尽内存，则可以从磁盘排序。
编辑：除非"上限"是指算法的O（n），这应该很容易弄清楚。