Facebook电面

Jester_Z 发表于 2016-1-30 08:18
想问一下楼主 这里面可能有负数吗

https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/

类似的题目哦。

Gianluigi 发表于 2016-1-30 09:05
https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/

类似的题目哦。

哈哈对 我就是下午做了这个题所以才有疑问的 有负数的话就不能滑动窗口了...

10楼的方法感觉应该是对的，复杂度怎么分析呢？

Jester_Z 发表于 2016-1-30 09:07
哈哈对 我就是下午做了这个题所以才有疑问的 有负数的话就不能滑动窗口了...

对啊  感觉如果有负数就不用判断target和sum，直接四种滑动情况或在一起了。

同求时间复杂度啊  感觉这个不太好分析啊，因为不知道滑动到底要滑动多久啊

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

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

echoruiko 发表于 2016-2-14 02:02
为什么“任意两点确定的submatrix的和，建立这个matrix用O(n^2)"呢？这样的matrix一共有n^4个吧。。？

注意是从左上角(0,0)位置开始的所有子矩阵。

wandonye 发表于 2016-2-14 04:56
注意是从左上角(0,0)位置开始的所有子矩阵。

哦哦~~谢谢~~但是10楼的方法只对non-negative的matrix有效吧？如果存在负数，就不能那样做了？

echoruiko 发表于 2016-2-14 05:21
哦哦~~谢谢~~但是10楼的方法只对non-negative的matrix有效吧？如果存在负数，就不能那样做了？

确实。看楼主后来回的几个帖子，应该是non-neg 的意思吧。。。

wandonye 发表于 2016-2-14 09:27
确实。看楼主后来回的几个帖子，应该是non-neg 的意思吧。。。

我后来在别的帖子看到这个题啦，说是non-negative的matrix~~谢谢啦~~