输入-数组/列表a,常数k
输出-最长子列表/带和<=k的子数组的长度
例如:给定
我是鲍勃
即数组[1,2,3]和k=3
子列表可能是[1],[2],[3],[1,2]
这里最长的子列表是[1,2]
长度=2
问题- TimeOut中的Hackerrank错误
循环- O(n)的时间复杂度-1
空间复杂度 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 00:25:18
通过更换时间密集的操作来解决这一问题。
当超过HackerRank为每个环境"HackerRank TimeOut“设置的时间限制时,就会发生超时。
溶液
用变量替换sum()函数
在最坏的情况下,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 lenmaxhttps://stackoverflow.com/questions/46626330
复制相似问题