首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >Tweet中最长的短语- Python超时

问Tweet中最长的短语- Python超时
EN

Stack Overflow用户
提问于 2017-10-08 00:13:59
回答 1查看 1.1K关注 0票数 1

输入-数组/列表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

EN

回答 1

Stack Overflow用户

发布于 2017-10-08 00:25:18

通过更换时间密集的操作来解决这一问题。

当超过HackerRank为每个环境"HackerRank TimeOut“设置的时间限制时,就会发生超时。

溶液

用变量替换sum()函数

在最坏的情况下,sum( list )将花费O(n^2)时间,如果所有时间都要对整个列表进行求和。

相反,维护变量意味着整个函数的O(n)等于更新变量的O(1)。

代码语言:javascript
复制
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
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/46626330

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档