和为S的连续正数序列:最直观的想法是,穷举法。使用res记录结果数组,使用temp记录临时数组,使用一个变量i枚举起始区间,由于要求的是连续正数序列,且序列至少包含两个数,故起始区间最多枚举到S的一半向下取整,使用一个变量j枚举结束区间,其范围由累加和控制,使用add表示区间内的数值和,首先判断区间内的累加和与目标和的大小关系,如果累加和大于目标和则退出内层循环,反之如果累加和等于目标和则清空之前的临时数组,并且将当前区间的数值依次加入到临时数组,再退出循环,从下一个起始区间开始枚举。
vector<vector<int> > FindContinuousSequence(int sum) { // 结果数组 vector<vector<int>> res; // 临时数组 vector<int> temp; // 序列至少两个数 最多从该数字一半向下取整开始枚举 int end=(sum-1)/2; // 枚举左区间 for(int i=1;i<=end;i++) { // 每个区间开始记录累加和add为0 int add=0; // 从左往后依次连续累加 右区间由累加和控制 for(int j=i;;j++) { add+=j; // 累加和大于目标和则退出 if(add>sum) break; // 累加和等于目标和则加入结果数组 else if(add==sum) { // 先将之前的临时数组清空 再存储当前数组 并加入到结果数组 temp.clear(); // 当前区间 起始下标为i 结束下标为j for(int k=i;k<=j;k++) temp.push_back(k); res.push_back(temp); break; } } } return res; }
优化:上述方法是首先枚举区间起始位置和区间结束位置,然后判断区间内数值累加和是否合法,如果合法再加入到临时数组。但是,连续整数序列是可以使用等差数列求和公式的!所以,不妨使用滑动窗口,由于序列至少两个数,所以窗口左边界指向1,窗口右边界指向2,且判断条件是区间左边界小于区间右边界,然后利用公式求当前窗口内的累加和,如果等于目标和,则清空临时数组,再根据左右边界,将其区间内的数值依次加入临时数组,再将临时数组加入结果数组,接着将左区间右移,反之如果大于目标和则将左区间右移,反之如果小于目标和则将右区间右移。
// left到right且d=1的等差数列求和公式为n*(left+right)/2 int add=(left+right)*(right-left+1)/2;
vector<vector<int> > FindContinuousSequence(int sum) { // 结果数组 vector<vector<int>> res; // 临时数组 vector<int> temp; // left表示区间左边界 right表示区间右边界 for(int left=1,right=2;left<right;) { // 等差数列求和公式 int add=(left+right)*(right-left+1)/2; // 累加和等于目标和 if(add==sum) { temp.clear(); for(int i=left;i<=right;i++) temp.push_back(i); res.push_back(temp); // 左区间右移 开始下一轮枚举 left++; } // 累加和小于目标和 else if(add<sum) // 右区间右移 right++; // 累加和大于目标和 else // 左区间右移 left++; } return res; }