非死不可 实习一面

之前的帖子写的太急了导致不太清楚，非常不好意思，我现在把详细的面经写一下。

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

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

补充内容 (2018-10-16 23:34):

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

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

楼主问一下第一题是包不包含负数的？包含负数的话怎么sliding window

补充内容 (2018-10-17 02:02):
看错了 长度为k的话有负数应该不影响 直接扫过去判断一下就行

wang021 发表于 2018-10-17 02:00
楼主问一下第一题是包不包含负数的？包含负数的话怎么sliding window

补充内容 (2018-10-17 02:02):

如果包含负数并且不规定subarray长度就在sum是负数的时候把sum清零，移动左指针到当前右指针的位置。
比如 [3,-1,4,-10,9] 当 左指针在index 0, 右指针走过-10的时候 sum = -4, 这时候先把左指针移动到9，sum清零继续往前走

def max_subarray_sum(nums):
    if not nums: return 0
    l, r = 0，0
    res = nums[0]
    curSum = 0
    while r < len(nums):
        if curSum < 0:
            curSum = 0
            l = r
        curSum += nums[r]
        r += 1
        res = curSum if curSum > res else res
    return res

求问第二题不用dp的话怎么优化到O(N)啊？

看来FB得准备两种方法解题

zy16373soup 发表于 2018-10-17 05:15
如果包含负数并且不规定subarray长度就在sum是负数的时候把sum清零，移动左指针到当前右指针的位置。
比 ...

题目不是规定了长度为s吗？

xiebw 发表于 2018-10-17 07:59
题目不是规定了长度为s吗？

嗯。。。只是讨论一下如果没有规定长度也可以用slicing window

感觉第二题是烙印高频题啊...
之前看到别的面筋有这道题也是烙印出的....

谢谢楼主分享！

第一题如果规定长度等于s，那对于长度n的数组，不就只有n-s+1个subarray吗… 为什么要用滑窗呢？还是说是长度<=s的subarray？

楼主最后怎么样？过了吗？