我想知道下面的代码有什么问题。在某些特定的场景中，它是否会消耗更多的时间？预期的时间复杂度：时间复杂度O（n）
def subArraySum(self,arr, n, s):
if sum(arr[0:n]) == s:
return [1, n]
if sum(arr[0:n]) < s:
return [-1]
start = 0
i =1
sum_elements = 0
while i < n:
sum_elements = sum(arr[start:i+1])
if sum_elements == s:
return [start+1, i+1]
if sum_elements < s:
i += 1
continue
if sum_elements > s:
start += 1
continue
if sum_elements < s:
return [-1]
1条答案
按热度按时间oxiaedzo1#
与在
while循环的每次迭代中运行sum(arr[start:i+1])不同，您应该使用一个变量，并在每次迭代中添加或减去子数组中包含或排除的相应值，这样您就可以避免O（n^2）的复杂度，并保持在O（n）内。目前，计算一个（可能很大的）子数组的总和会有很多开销，该子数组在每次迭代的开始或结束时只改变了一个值。