带有嵌套 for 循环的 Python 代码太慢

Question

我正在做 problem来自 HackerRank。本题首先定义了一个大小为 n 的零数组，然后对其进行运算。假设数组是 x = [0, 0, 0, 0, 0, 0]。所以 n = 6 这里。现在考虑操作(他们在问题中称之为查询)[1, 2, 5]。这意味着在数组 x 中，从索引 0 到 1 添加 5。所以 x 现在变成 x = [5, 5, 0, 0, 0, 0]。并且可能有很多这样的操作(查询)。最后，我们只需要找到最终数组 x 的最大元素。所以样本输入是

5 3
1 2 100
2 5 100
3 4 100

所以我们需要有大小为 5(初始化为零)的数组 x，并且要在其上运行 3 个查询。如果我们通过查询，我们发现最终数组中的最大元素是 200。我在这里使用嵌套 for 循环完成了代码。外层 for 循环遍历查询，内层 for 循环操作数组 x。 对于 x 数组大小的小值，我的代码运行良好。但是当 n = 1000000 和查询数 m = 100000 时，嵌套的 for 循环将永远运行(它就像一个无限循环)。我想知道如何使它更快。 以下是嵌套的for循环

# Construct a zero list of length n
worklist = list([0]*n)
# Loop through the queries
for query in queries:
    # Since the problem defines the queries vector
    # as one based index, we need to modify the
    # indices of query
    index0, index1 = query[0]-1, query[1]-1
    # Now construct the new list with addition
    for i in range(index0, index1+1):
        worklist[i] = worklist[i] + query[2]

我想我需要修改我的算法来做到这一点。欢迎提出建议。

Answer 1

在这个问题的讨论页面中，有一个 O(n) 的解决方案， 这是关于重叠的问题。

基本思路是，你只需要在数组中标记“添加”点和“删除”点，所以最后阶段你只需要遍历一次数组并将“当前总和”保留在当前索引中，你可以记录最大的答案。

例如 5 3

1 2 100

2 5 100

3 4 100

你的数组将简化为

0, 0, 0, 0, 0, 0

---

当获取第一条输入记录时(1 2 100):

100, 0, -100, 0, 0, 0

这意味着当你做最后的扫描总和总结时，你的循环将在步骤中计算

索引 0，总和 100

索引1，总和100

索引 2，总和 0

索引 3，总和 0 ...

---

当获取第二个输入记录时(2 5 100):

100, 100, -100, 0, 0, -100

这意味着当你做最后的扫描总和总结时，你的循环将在步骤中计算

索引 0，总和 100

索引1，总和200

索引2，总和100

索引3，总和100

索引4，总和100

索引 5，总和 0

因此最大值发生在索引 1 处，

---

当取第二个输入记录时(3 4 100):

100, 100, 0, 0, -100, -100

这意味着当你做最后的扫描总和总结时，你的循环将在步骤中计算

索引 0，总和 100

索引1，总和200

索引2，总和200

索引3，总和200

索引4，总和100

索引 5，总和 0

因此最大值发生在索引 1 处，