我需要一个连续子数组的函数，其运行时复杂度为 n polylog n （算法）

Question

我正在与一个小组一起做一项作业，我们应该在其中创建连续的子数组，其中我们有一个

tMin

，

tMax

，它为我们提供了适合最小值和最大值之间的匹配的“对”。我们有一个输入 .txt 文件，它从中读取可能的匹配项并将其作为整数输出到单独的 output.txt 文件中。问题是它希望我们从 O(n^2) 变为 O(n polylog n)

import time

def number_of_allowable_intervals(input_file_path, output_file_path):
    # Open input file and read values
    with open(input_file_path, 'r') as input_file:
        # Read the size of the array and allowable range
        n, tmin, tmax = map(int, input_file.readline().strip().split(','))
        A = list(map(int, input_file.readline().replace(',', '').split()))

    # Count all subarrays within the range [tmin, tmax]
    sub_array_count = 0

    start_time = time.time()

    for i in range(len(A)):
        current_sum = 0
        for j in range(i, len(A)):
            current_sum += A[j]

            # Check if the sum is within the range [tmin, tmax]
            if tmin <= current_sum <= tmax:
                sub_array_count += 1

    end_time = time.time()


    print("Runtime:", end_time - start_time)

    with open(output_file_path, 'w') as output_file:
        output_file.write(str(sub_array_count))

if __name__ == "__main__":
    input_path = "input.txt"
    output_path = "output.txt"
    number_of_allowable_intervals(input_path, output_path)

这是输入.txt

10, 0, 0
-1, 1, -1, 1, -1, 1, -1, 1, -1, 1000

预期结果应该是 20。

这就是我们所拥有的。我们尝试过二分搜索，我们尝试过 AVLtree，但我们实际上无法找到一种方法来让它真正发挥作用。我们将不胜感激任何我们能得到的帮助。请并谢谢你。

Answer 1

    for i in range(len(A)):
        current_sum = 0
        for j in range(i, len(A)):
            current_sum += A[j] ...

哇，正在进行大量的重新计算， 考虑到你永远不会变异

A

。

仅计算一次累积和， 边走边将它们存储在暂存向量中。 成本是 O(N) 线性的。

然后在扫描时使用它，同样具有线性成本。 你可能会发现偶尔明智的减法 会帮助你适应这些

已缓存 结果满足您的需求。