狗家店面

zhrobinson

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由 zhrobinson 于 2019-11-1 02:56 编辑

新鲜狗家店面
面试人听口音是中东或者欧洲人，非华人或印度裔。小哥挺nice，pace比较慢不会催，但是通话质量真心不好，听不清楚
上题：

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

上来先用brute force, 之后优化算法到O(N)。分析了几种算法的时间空间复杂度。只有一题，连说带写花了30分

我的解法

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

黎明之前

这题lc有，非负数用sliding window，有负数是道hard用单调栈

yiliaobailiao

本帖最后由 yiliaobailiao 于 2019-11-1 08:03 编辑

有负数的时候，是会有问题的。比如说 [1, 1, 1, 1, -100, 1, 1, 1], target = 3。因为有负数存在的可能性，所以当和大于target的时候，是不能直接去掉队尾的元素的。

codyman

这题prefix sum数组不就可以解了吗，负数也ok啊

不知道小帅

感觉可以用sliding window处理

zhrobinson

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

不知道小帅

不太明白这里如果是负数的话怎么handle，加上新元素大于target，万一下一个是负的，然后加上之后正好等于呢。。

xu2011

需要assume positive integer把

小葱头丫

感觉负数handle不了？

xy666

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

xy666

黎明之前发表于 2019/11/02 00:41:17
这题lc有，非负数用sliding window，有负数是道hard用单调栈

不一样，有负数情况比lc那题难，因为那题求最短容易做到均摊线性查询单调队列，这题用一样思路需要在单调栈里二分。进一步优化到线性看我回帖