题解 | #和为S的连续正数序列#
和为S的连续正数序列
http://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe
方法一：暴力解法
区间左边界 i
区间右边界 j
用枚举区间[i, j]，来计算区间和，看是否等于目标sum
复杂度分析：class Solution { public: vector<vector<int> > FindContinuousSequence(int sum) { vector<vector<int>> ret; // 左边界 for (int i=1; i<=sum/2; ++i) { // 右边界 for (int j=i+1; j<sum; ++j) { int tmp = 0; // 区间 [i j] for (int k = i; k<=j; ++k) { tmp += k; } if (sum == tmp) { vector<int> ans; for (int k=i; k<=j; ++k) ans.push_back(k); ret.push_back(ans); } else if (tmp > sum) { break; } } } return ret; } };
时间复杂度 O(N的3次方)
空间复杂度 O(1)
方法二：滑动窗口
解题思路：连续子序列问题，最优解法就是滑动窗口的使用。
确定左右边界left right，滑动窗口确定区间范围，sum小于target右移，大于则左移，注意等于的时候加入结果的同时要左移缩小边界，继续统计下一组结果
这里的题意隐藏条件 没有给定具体的数组num 我们可以通过下标关联[1,2,3,4,5,6,7....]
代码如下：已经加上详细的注释了
import java.util.ArrayList;
public class Solution {
public ArrayListFindContinuousSequence(int sum) {
ArrayList< ArrayList> res = new ArrayList<>();
// 窗口 win 左边界 left 右边界 right
int left = 1;
int right = 1;
int win = 0; // 窗口 win 中数字之和
while( left <= (sum/2) ){ // left 左边界的有效范围 【有剪枝】 // 一直循环判断 win 和 sum 的大小关系 if(win == sum){ // 把当前的结果收集起来 ArrayListlist = new ArrayList<>();
for(int i=left;isum){
// 把窗口中左边的元素去掉 （2个操作）
win = win - left;
left++;
}else{ // win < sum // 窗口值增加 right向右移动 win = win + right; right++; } } return res; } } 图示操作：一直循环着向前进
终止条件：有剪枝操作，left <= sum/2
自己可以分 sum 为奇数偶数，得出最终结论。举例即可！
复杂度分析：
时间复杂度 O(N) ： 其中 N = sum ；
空间复杂度 O(1) : 只有几个常量而已！
投递小米集团等公司10个岗位 >
元戎启行公司福利 3689人发布
查看5道真题和解析