CSES子数组和II：CPython3与PyPy3的TLE差异及优化咨询

你的代码逻辑是正确的——通过前缀和+哈希表统计符合条件的子数组数量，但在CPython3和PyPy3中出现不同测试用例超时的情况，核心原因是哈希表的性能稳定性差异以及IO开销在不同环境下的表现不同。以下是具体分析和优化方向：

为什么会出现跨环境超时？ #

测试用例规模均为2×10^5，但不同用例的前缀和分布不同：

• PyPy3超时用例25：大概率是该用例的前缀和几乎全为唯一值，PyPy的字典实现处理大量唯一键时，哈希表扩容、哈希计算的开销比CPython更大，导致超时。
• CPython3超时用例26、27：这两个用例可能前缀和重复率高，但CPython的IO操作（多次readline）开销累积，加上字典的部分额外开销，最终导致超时。

优化方向与实现 #

1. 输入读取优化（针对CPython） #

CPython的IO性能较弱，多次readline会产生额外系统调用开销。改用一次性读取全部输入的方式，能显著降低IO耗时：

from sys import stdin, stdout

def main():
    data = list(map(int, stdin.read().split()))
    n = data[0]
    x = data[1]
    arr = data[2:2+n]
    
    d = {0: 1}
    curr_sum = 0
    ans = 0
    
    for num in arr:
        curr_sum += num
        ans += d.get(curr_sum - x, 0)
        d[curr_sum] = d.get(curr_sum, 0) + 1
    
    stdout.write(str(ans))

if __name__ == "__main__":
    main()

2. 替换哈希表为二分查找（稳定兼容PyPy/CPython） #

哈希表的性能依赖于键的分布，最坏情况可能退化为O(n²)。改用有序前缀和数组+二分查找的方案，能保证O(n log n)的稳定时间复杂度，不受前缀和分布影响：

from sys import stdin, stdout
import bisect

def main():
    data = list(map(int, stdin.read().split()))
    ptr = 0
    n = data[ptr]
    ptr += 1
    x = data[ptr]
    ptr += 1
    arr = data[ptr:ptr+n]
    
    prefix = [0]
    curr_sum = 0
    ans = 0
    
    for num in arr:
        curr_sum += num
        target = curr_sum - x
        # 二分查找目标值的左右边界，计算出现次数
        left = bisect.bisect_left(prefix, target)
        right = bisect.bisect_right(prefix, target)
        ans += right - left
        # 将当前前缀和插入有序数组
        bisect.insort(prefix, curr_sum)
    
    stdout.write(str(ans))

if __name__ == "__main__":
    main()

3. 代码结构优化（针对PyPy） #

PyPy对局部变量的访问速度远快于全局变量，将代码包裹在main函数中执行，能减少全局变量的额外开销。

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