G家题目讨论：所有的subarray sum 在一个区间 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

G家题目讨论：所有的subarray sum 在一个区间

G家题目讨论：所有的subarray sum 在一个区间# JobHunting - 待字闺中

x*i2014-01-19 08:01

1 楼

给一个array of int，以及一个range (low, high)，找出array中
所有的subarray使得这个subarray的和在range之中。array可以有负数
这个O(N^2),
for i= 0 to N,
for j= i to N
check sum(i, j) is in range. // add num[j] to previous sum(i, j-1)
有更好的方法吗？

a*22014-01-19 08:01

2 楼

divide and conquer.
分段找，中间合并检查，n*logn。

【在 x*******i 的大作中提到】

: 给一个array of int，以及一个range (low, high)，找出array中
: 所有的subarray使得这个subarray的和在range之中。array可以有负数
: 这个O(N^2),
: for i= 0 to N,
: for j= i to N
: check sum(i, j) is in range. // add num[j] to previous sum(i, j-1)
: 有更好的方法吗？

x*i2014-01-19 08:01

3 楼

有种极限情况，range很大，所有subarray sum都在里面，总数是n^2级别的
这应该是下限吧

★ 发自iPhone App: ChineseWeb 8.2.2

【在 x*******i 的大作中提到】

s*z2014-01-19 08:01

4 楼

是的, 当结果都是N^2的时候, 复杂度应该低不了N^2

b*p2014-01-19 08:01

5 楼

一个一个加起来，sum array排序，然后两个指针一个从头一个从屁股扫一下就好了。

s*t2014-01-19 08:01

6 楼

还是n2啊

【在 b****p 的大作中提到】

: 一个一个加起来，sum array排序，然后两个指针一个从头一个从屁股扫一下就好了。

k*z2014-01-19 08:01

7 楼

dp，求出以第i个元素结尾的subarray，之后memoize下来，然后第i+1个元素是以第i个
元素的subarray为基础，加上第i+1个元素的weight，如果仍然符合要求，那么就
memoize，否则就抛弃，这样子只要遍历一次n就解决战斗了，running time是和输出结
果的个数有关，假设输出结果是m，那running time就是O(m + n)

F*92014-01-19 08:01

8 楼

你这样会漏掉一些解吧。比如合并【2 -5】【6-7】时会漏了【4-6】等可能的解呀
。

【在 a*********2 的大作中提到】

: divide and conquer.
: 分段找，中间合并检查，n*logn。

a*22014-01-19 08:01

9 楼

不会。
比如对区间[begin, end)，mid=(begin+end)/2，分段，[begin, mid), [mid, end).
所求区间或者在这两个子段中不胯mid，或者是跨mid的区间。跨mid的区间O(n)找到。
总的复杂度O(n lg n)，详情见introduction to algorithm third edition chapter 1
.4中对subarray的分析。

【在 F********9 的大作中提到】

:
: 你这样会漏掉一些解吧。比如合并【2 -5】【6-7】时会漏了【4-6】等可能的解呀
: 。

x*i2014-01-19 08:01

10 楼

"跨mid的区间O(n)找到。"
这个不行吧？比如说左边（1 ，2， 3），右边（4， 5 ，6），range (0, 100),
那跨中间的组合是 9种 {(3, 4), (3,4, 5), (3,4,5,6), (2,3,4)...}， n^2.

1

【在 a*********2 的大作中提到】

: 不会。
: 比如对区间[begin, end)，mid=(begin+end)/2，分段，[begin, mid), [mid, end).
: 所求区间或者在这两个子段中不胯mid，或者是跨mid的区间。跨mid的区间O(n)找到。
: 总的复杂度O(n lg n)，详情见introduction to algorithm third edition chapter 1
: .4中对subarray的分析。

f*t2014-01-19 08:01

11 楼

【在 x*******i 的大作中提到】

c*n2014-01-19 08:01

12 楼

这样不行吧。
比如 dp[i]+num[i+1] 不在range中不代表 dp[i+1] 不存在啊。（可以drop之前的元素）

【在 k******z 的大作中提到】

: dp，求出以第i个元素结尾的subarray，之后memoize下来，然后第i+1个元素是以第i个
: 元素的subarray为基础，加上第i+1个元素的weight，如果仍然符合要求，那么就
: memoize，否则就抛弃，这样子只要遍历一次n就解决战斗了，running time是和输出结
: 果的个数有关，假设输出结果是m，那running time就是O(m + n)

x*92014-01-19 08:01

13 楼

数组长度为N，把整个数组分为K段。这里取 K=sqrt(N)。
一段子数组我们用[st, end]来表示。
我们要统计每段子数组[st...x]的取值。
例如，[1, 2, 3]。sum([1]) = 1, sum([1, 2]) = 3, sum([1, 2, 3]) = 6。然后排
序累加，使得类似“这一段子数组在和大于3有多少个”的Query的时间复杂度为O(log(
K))。
然后遍历数组，通过预处理好的子数组序列进行计算。
预计时间复杂度为O(n * sqrt(n) * log(n))。
比O(n^2)要好一点。不过比较难写。。。=。=