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