CSES Python在Cpython3/PyPy3中的不同TLE

Question

我正在尝试做CSES的子数组和问题 - https://cses.fi/problemset/task/1661，我对逻辑很有信心，但在CPython和PyPy3中得到的运行时间超限（TLE）结果却不一样。

这是我的代码：

from sys import stdin, stdout
 
_, x = list(map(int,stdin.readline().split()))
arr = list(map(int,stdin.readline().split()))
 
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))

这是我在PyPy3中的结果：

这是我在CPython3中的结果：

描述：

• 在PyPy3中，第25个测试用例超时了，但第26和第27个测试用例在0.2秒内通过了。
• 在CPython3中，第25个测试用例通过了，耗时0.85秒，但第26和第27个测试用例超时了。

这三个测试用例的输入大小都是2*10^5。

我觉得逻辑是正确的，但我想看看我是否遗漏了什么，或者是否还有其他优化的方法可以尝试。

Answer 1

你可能想把你的代码放进一个函数里。因为局部变量的访问速度比全局变量快，而你经常需要用到 d、curr_sum、ans 和 num 这些变量。

除此之外，你的代码看起来优化得不错。

from sys import stdin
 
def solve(x, arr):
    d = {0: 1}
    curr_sum = 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
    return ans

_, x = list(map(int,stdin.readline().split()))
arr = list(map(int,stdin.readline().split()))
print(solve(x, arr))

如果你在使用 Python3 或 PyPy3 时仍然遇到超时的问题，建议你联系一下题目的作者。可能他们不小心设置了过于严格的时间限制，或者这个题目不支持 Python3 和 PyPy3。