最长短语 - Python的超时

输入 - 阵列/列出，常数k最长短语 - Python的超时

输出 - 最长子列表的长度/子阵列与总和< = K

例如给定

我鲍勃

即阵列[1,2,3]且k = 3个

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

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

长度 = 2

问题 - 在Python超时错误上Hackerrank

时间复杂度 - 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

来源

2017-10-08 Chaitanya Bapat

代码的实际问题是什么？ hackerrank超时并不是问题。 – James

看起来好像超过了执行特定测试用例的限制。因此必须通过消除时间密集型操作来解决这个问题。例如整个列表的总和 –

解决它通过更换时间密集型操作

Tim当它超过由HackerRank为每个环境中设置的时限发生电子出"HackerRank TimeOut"

解

由可变

替换sum（）函数在最坏的情况下，总和（列表）将需要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

来源

2017-10-08 00:25:18

最长短语 - Python的超时

回答

相关问题