买它店面

今天刚面试


第一题很像舞遛零，但是多了一个里面数值大于零的条件。

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

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

用额外的资料结构。

匿名用户 发表于 2024-11-1 23:00
感谢分享，已加米，请问能简单说一下大于零跟two pointer有啥关系吗？ 要是把左右指针中间的都加起来的话 ...

如果所有数值大于零，挪动 right pointer guarantees increament in subarray sum, 挪动 left pointer vice versa

当 subarray < k，++right 直到 subarray sum >= k, 当 subarray sum > k, ++left

求问第二题有follow up吗？要求time O(N)吗

请问第一题怎么做呢

MTTTT 发表于 2024-11-1 22:35
求问第二题有follow up吗？要求time O(N)吗

没有follow-up 只问了时间複杂度。最佳解是O(n)。有可能是时间不够所以没问

zzrdwj 发表于 2024-11-1 23:00
请问第一题怎么做呢

标准解法用prefix sum 如果有大于零条件，可以用two pointers

frizfealer 发表于 2024-11-01 20:35:02
标准解法用prefix sum 如果有大于零条件，可以用two pointers

感谢分享，已加米，请问能简单说一下大于零跟two pointer有啥关系吗？ 要是把左右指针中间的都加起来的话，大不大于零也没什么区别呀，只能是遇见大于k的，两个指针都挪到后面去，对时间空间好像也没啥影响呢

所以是bbg不是买它是吗

匿名用户 发表于 2024-11-2 02:08
所以是bbg不是买它是吗

是买它店面 可能按错了导致出现BBG

更新：后来hr说move forward 我的情况一题没有写出最佳解