例如，我们得到长度为5（n=5）的字符串“number”，它由从1到a的所有数字组成（数字可以重复，但从1到a的所有数字必须包含在字符串中，并且字符串的长度必须为n）。假设a=2，并用先前给定的条件生成示例数字（或者更确切地说是数字序列），设其为“12211”，长度为5，由1和2组成现在假设我们需要找到一个算法，在字符串“Number”中找到所有可能的数字序列，其中每个序列都是“Number”的子串，每个序列的长度不同，可能只包含任何数字的一次出现。
对于我们的示例“12211”，我们可以说有7个序列：
1. "1"
2. "12"
3. "2"
4. "2"
5. "21"
6. "1"
7. "1"
结果将是“7”。
另一个清晰的例子是：对于“数字”=“123452”和B=5（数字是1,2,3,4,5），可能的序列是：
1. "12345"
2. "1234"
3. "123"
4. "12"
5. "1"
6. "2345"
7. "234"
8. "23"
9. "2"
10. "3452"
11. "345"
12. "34"
13. "3"
14. "452"
15. "45"
16. "4"
17. "52"
18. "5"
19. "2"
结果将是“19”。
你对快速算法有什么想法吗？我想到的那个太慢了（比较每个数字）。
最佳答案
将布尔表设为集合（在第n个元素中为true表示n在实际间隔中）
现在很容易了。您只需遍历数组并扩展间隔，当您找到重复的元素时，只需移动间隔的开始部分，直到达到唯一的序列。
一些更好的解释代码：
unsigned long long number_of_seq(string seq) {
set<char> in_use; //Can be some O(1) set, pointless
unsigned long long result = 0ULL;
//p - begin of actual interval
//q - end of this interval
for(size_t p = 0, q = 0; q < seq.size();) {
while(in_use.count(seq[q]) != 0) { //While: add seq[q] makes interval not unique
in_use.erase(seq[p]);
++p; //move begin of interval
}
in_use.insert(seq[q]);
++q;
result += q - p; //add size of interval
}
return result;
}
您应该添加任何间隔的大小，因为您只需在末尾添加新元素，所有子字符串都是正确的（没有两个相同的字符），并且考虑所有没有新字符的子字符串它是seq[0:q]和seq[q]中最大的唯一子串，所以它是正确的。