python - 推文中最长的短语 - Python 超时

Question

输入 - 数组/列表a，常量k

输出 - 总和 <=k 的最长子列表/子数组的长度

例如给出

I am Bob

即数组 [1,2,3] k=3

可能的子列表是 [1],[2],[3],[1,2]

这里最长的子列表是[1,2]

长度 = 2

问题 - Hackerrank 上 Python 中的超时错误

时间复杂度 - 1 for 循环 - O(n)

空间复杂度 O(n)

def maxLength(a, k):
lenmax=0
dummy=[]
for i in a:
dummy.append(i)
if sum(dummy)<=k:
lenmax=max(lenmax,len(dummy))
else:
del dummy[0]
return lenmax

Answer 1

通过替换耗时操作解决了

超过HackerRank为每个环境设置的时间限制时发生超时"HackerRank TimeOut"

解决方案

Replace sum() function by a variable

在最坏的情况下，如果要一直对整个列表求和，则 sum(list) 将花费 O(n^2) 时间。

相反，维护变量意味着整个函数的 O(n) 与更新变量的 O(1) 一样。

def  maxLength(a, k):
lenmax=0
dummy=[]
sumdummy=0
for i in a:
    dummy.append(i)
    sumdummy+=i
    if sumdummy<=k:
        lenmax=max(lenmax,len(dummy))
    else:
        sumdummy-=dummy[0]
        del dummy[0]

return lenmax