x*******i
发帖数: 26 | 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*********2
发帖数: 194 | 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*******i
发帖数: 26 | 3 有种极限情况，range很大，所有subarray sum都在里面，总数是n^2级别的
这应该是下限吧
★ 发自iPhone App: ChineseWeb 8.2.2
【在 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)
: 有更好的方法吗？
| s*******z
发帖数: 83 | 4 是的, 当结果都是N^2的时候, 复杂度应该低不了N^2 | b****p
发帖数: 216 | 5 一个一个加起来，sum array排序，然后两个指针一个从头一个从屁股扫一下就好了。 | s******t
发帖数: 229 | 6 还是n2啊
【在 b****p 的大作中提到】
: 一个一个加起来，sum array排序，然后两个指针一个从头一个从屁股扫一下就好了。
| k******z
发帖数: 4 | 7 dp，求出以第i个元素结尾的subarray，之后memoize下来，然后第i+1个元素是以第i个
元素的subarray为基础，加上第i+1个元素的weight，如果仍然符合要求，那么就
memoize，否则就抛弃，这样子只要遍历一次n就解决战斗了，running time是和输出结
果的个数有关，假设输出结果是m，那running time就是O(m + n) | F********9
发帖数: 44 | 8
你这样会漏掉一些解吧。 比如合并 【2 -5】 【6-7】时会漏了 【4-6】等可能的解呀
。
【在 a*********2 的大作中提到】
: divide and conquer.
: 分段找，中间合并检查，n*logn。
| a*********2
发帖数: 194 | 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*******i
发帖数: 26 | 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**********t
发帖数: 1001 | 11
【在 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)
: 有更好的方法吗？
| c******n
发帖数: 100 | 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*******9
发帖数: 138 | 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)要好一点。不过比较难写。。。=。= |
|
