p*3
1 楼
给一个数组和一个目标数s
找出所有和为s的子数组
例如 [3,1,2,-1,-2], s=3
[[3],[1,2],[3,1,2,-1,-2]]
这题能做到优于O(n^2)么?
换句话说能不用检查所有的子数组么?
找出所有和为s的子数组
例如 [3,1,2,-1,-2], s=3
[[3],[1,2],[3,1,2,-1,-2]]
这题能做到优于O(n^2)么?
换句话说能不用检查所有的子数组么?
r*h
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)么?
: 换句话说能不用检查所有的子数组么?
【在 p****3 的大作中提到】
: 给一个数组和一个目标数s
: 找出所有和为s的子数组
: 例如 [3,1,2,-1,-2], s=3
: [[3],[1,2],[3,1,2,-1,-2]]
: 这题能做到优于O(n^2)么?
: 换句话说能不用检查所有的子数组么?
r*n
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)解。
然后这题就变成了找两个indices i, j, i<=j, such that sum[j] - sum[i] = s，这
个是2-sum problem的变体，可以有O(N)解。
r*e
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*********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
5 楼
我一开始也想的是不连续
不连续的话就是NP问题了吧
【在 r*******e 的大作中提到】
: 赞
: 我想成下标不连续的了
不连续的话就是NP问题了吧
【在 r*******e 的大作中提到】
: 赞
: 我想成下标不连续的了
c*a
6 楼
下标不连续的话就先排序，再递归
相关阅读
To those who are eager for a job怎么找政府的工作?Dirty and Quick Survey有人面过bloomberg吗？第一次phone interview,我彻底搞砸了关于医疗保险H1b能不能同时给两个公司做事？opt最多每周多少小时Immediate Opening for Senior SAS Programmer (Enterprise Gui请大家谈谈应对简单题目的策略吧面试遇到常见题怎么处理？请教关于OPT的问题Openning for entry level ASIC engineer2人小公司超低工资part time H1b approved + 推荐律师这是骗子公司吗？服装问题Faculty On-Site后，多久会有消息啊？请教 Thank you letter after interview怎么估计backtracking的复杂度？Bloomberg 面经