GenomicRangeQuery题解 循环判断in列表与转set的时间复杂度对比

首先明确结论：你对两种写法的理论时间复杂度判断是正确的，你第一种写法被平台判定为O(N+M)属于测试用例覆盖不全导致的误判。

第一种写法的实际运行逻辑 #

你写的第一种解法中，x in 字符串操作在Python中是有提前终止逻辑的：遍历字符串时只要匹配到目标字符就会立刻返回True，不会走完整个子串。

• 你的判断顺序是A→C→G→T，刚好对应impact因子从小到大的顺序，只要子串里存在更小的impact因子，搜索就会提前结束。
• Codility的公开测试用例普遍设置了A、C这类小impact因子出现频率很高的场景，大部分查询的in操作只需要遍历少数几个字符就能得到结果，平均开销接近常数级，因此平台的复杂度检测工具误判为了O(N+M)。
• 但该写法的最坏时间复杂度仍然是O(NM)：比如当S全是字符T，且每个查询的范围都是整个S串时，每次A in S、C in S、G in S都要遍历完整个长度为N的串才能返回False，总开销就是O(MN)，如果测试用例有这种极端场景，你的解法是无法通过的。

转set写法的时间复杂度逻辑 #

你最初把切片转set的写法，理论时间复杂度确实是O(N*M)：

• 把字符串切片转set的过程没有提前终止逻辑，必须遍历完切片里的所有字符才能完成set的构建，哪怕切片第一个字符就是A，也需要走完整个切片。
• 每次查询的固定开销等于切片长度，最坏情况下每次切片长度都是N，总复杂度就是O(N*M)，没有优化空间，因此平台不会误判。

真正的O(N+M)解法思路 #

这道题标准的O(N+M)解法是前缀和预处理：

1. 先预处理4个长度为N+1的前缀计数数组，分别统计到每个位置为止，A、C、G、T四个字符累计出现的次数，这一步开销是O(N)
2. 每个查询只需要用区间右端点的计数减去左端点前一位的计数，就能快速判断区间里是否存在对应字符，每次查询开销O(1)，M次查询总开销O(M)
3. 整体复杂度就是O(N+M)，没有最坏情况的性能问题

内容的提问来源于stack exchange，提问作者shihs