p****3
发帖数: 448 | 1 给一个数组和一个目标数s
找出所有和为s的子数组
例如 [3,1,2,-1,-2], s=3
[[3],[1,2],[3,1,2,-1,-2]]
这题能做到优于O(n^2)么?
换句话说能不用检查所有的子数组么? | r**h
发帖数: 1288 | 2 元素非负的话好像可以O(n)
【在 p****3 的大作中提到】
: 给一个数组和一个目标数s
: 找出所有和为s的子数组
: 例如 [3,1,2,-1,-2], s=3
: [[3],[1,2],[3,1,2,-1,-2]]
: 这题能做到优于O(n^2)么?
: 换句话说能不用检查所有的子数组么?
| r*********n
发帖数: 4553 | 3 定义一个int sum[N]数组，sum[i] = arr[0]+arr[1]+...+arr[i]
然后这题就变成了找两个indices i, j, i<=j, such that sum[j] - sum[i] = s，这
个是2-sum problem的变体，可以有O(N)解。 | r*******e
发帖数: 7583 | 4 赞
我想成下标不连续的了
【在 r*********n 的大作中提到】
: 定义一个int sum[N]数组，sum[i] = arr[0]+arr[1]+...+arr[i]
: 然后这题就变成了找两个indices i, j, i<=j, such that sum[j] - sum[i] = s，这
: 个是2-sum problem的变体，可以有O(N)解。
| r**h
发帖数: 1288 | 5 我一开始也想的是不连续
不连续的话就是NP问题了吧
【在 r*******e 的大作中提到】
: 赞
: 我想成下标不连续的了
| c******a
发帖数: 789 | |
|
