fb 7月电面

飞仙公子 发表于 2016-9-3 02:25
老白～～～～～～

老白有时候真的很是操蛋啊。。

“subarray sum to K”
忘了是leetCode那道题了，每次滑动窗口，看之前那堆的值 减去移出的 + 新 加入的 是不是等于target
第二题也没印象是哪到真题了。

cicean 发表于 2016-9-3 14:37
“subarray sum to K”
忘了是leetCode那道题了，每次滑动窗口，看之前那堆的值 减去移出的 + 新 加入的  ...

应该 是这题 把 325. Maximum Size Subarray Sum Equals k
size 0 就false 有 等于的就 true 吧 也不用最大了

飞仙公子 发表于 2016-8-15 13:21
O(n)的解法，类似two sum啊

为啥不是O（n^2）? subarray不是两端都要遍历的吗。。

kwang1993 发表于 2016-9-3 22:30
为啥不是O（n^2）? subarray不是两端都要遍历的吗。。

1，2，3，4，5，类似two sum，维持当前和1,3,6,10,15, 如果当前和为k或者当前和减去之前的一个和为k，则返回true。。。本质不就是two sum问题吗？ 用set维持当前和，不需要用map，节省空间

飞仙公子 发表于 2016-9-3 22:46
1，2，3，4，5，类似two sum，维持当前和1,3,6,10,15, 如果当前和为k或者当前和减去之前的一个和为k，则 ...

这样的话，对每个数求当前和并与k比较 [ O（n）]，对每个当前和 遍历之前的所有当前和，分别做差和k比较 [ O（n）]，还是O（n^2）。。。

补充内容 (2016-9-4 09:39):
我是不是哪里没搞清楚？

kwang1993 发表于 2016-9-4 09:25
这样的话，对每个数求当前和并与k比较 [ O（n）]，对每个当前和 遍历之前的所有当前和，分别做差和k比较  ...

是。。。。请刷leetcode第一题，two sum

飞仙公子 发表于 2016-9-4 09:45
是。。。。请刷leetcode第一题，two sum

关键点是在于用set存储和的数组，看当前和－k是否在set里就好了，O(1)

飞仙公子 发表于 2016-8-16 11:38
已挂。。想静静

啥挂了？

飞仙公子 发表于 2016-9-4 09:48
关键点是在于用set存储和的数组，看当前和－k是否在set里就好了，O(1)

原来不是连续 元素 subarray。