推特 OA test 4

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
具体见截图

aangel 发表于 2017-8-14 12:17
第三题能想到O(N^2)的方法，还有更快的吗？

有O(n) 的方法，http://www.geeksforgeeks.org/sum-of-all-subarrays/这里

第三题能想到O(N^2)的方法，还有更快的吗？

求解法 赞赞赞赞赞赞

aangel 发表于 2017-8-14 12:17
第三题能想到O(N^2)的方法，还有更快的吗？

把O(n^2)的求和公式写出来，然后化成前缀合的表达式，再用一些特别的求和方式，应该可以有O(n)算法

finger 发表于 2017-8-22 03:55
有O(n) 的方法，http://www.geeksforgeeks.org/sum-of-all-subarrays/这里

谢谢 非常有用的链接！