题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
返回值描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
示例1
输入
9
返回值
[[2,3,4],[4,5]]
思路
方法四：按序列大小遍历
这道题我又想了一下，感觉上一篇文章方法三对a进行遍历还是不够快。因为如果sum为100的话，a要遍历50次。但事实上倒数第一个可能的a肯定小于50，因为两个数相加等于100，那a一定小于sum/2。倒数第二个可能的a肯定小于32，因为三个数相加等于100，那a一定小于sum/3-1。这样的话我只需要遍历到sum/n-(n-1)/2<1的时候就好。通过n+(n*n-n)/2 > sum解出n=14，相比50次要小很多。
在这个基础上，如果我们利用以下三个定理，就可以排除更多的选项。
- 当n为偶数时，n个连续的数相加一定不能被n除尽
- 当n为偶数时，n个连续的数相加再加n/2一定能被n除尽
- 当n为奇数时，n个连续的数相加一定能被n除尽
以100为例，整个遍历过程就是这样的：
1. 100可以被2整除，所以2个连续的数不可能加起来等于100
2. 100不可以被3整除，所以3个连续的数不可能加起来等于100
3. 100可以被4整除，所以4个连续的数不可能加起来等于100
4. 100可以被5整除，所以5个连续的数可能加起来等于100
a = 100/5-(5-1)/2 = 18; b = a+n-1 = 22
5. 100+6/2不可以被6整除，所以6个连续的数不可能加起来等于100
6. 100不可以被7整除，所以7个连续的数不可能加起来等于100
7. 100+8/2可以被8整除，所以8个连续的数可能加起来等于100
a = 100/8-(8-1)/2 = 9; b = a+n-1 = 16
8. 100不可以被9整除，所以9个连续的数不可能加起来等于100
9. 100可以被10整除，所以10个连续的数不可能加起来等于100
10. 100不可以被11整除，所以11个连续的数不可能加起来等于100
11. 100+12/2不可以被12整除，所以12个连续的数不可能加起来等于100
12. 100不可以被13整除，所以13个连续的数不可能加起来等于100
13. 100+14/2不可以被14整除，所以14个连续的数不可能加起来等于100
我觉得新的这个方法在数字特别大的时候可以更快地解决这个问题。
题解：
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int> > ans;
for(int n=2;n+(n*n-n)/2<=sum;n+=1){
int a,b;
if(n%2==0 && (sum+n/2)%n == 0 || n&1 && sum%n == 0){
a = sum/n - (n-1)/2;
b = a+n-1;
vector<int> temp;
for(int i=a;i<=b;i++){
temp.push_back(i);
}
ans.push_back(temp);
}
}
reverse(ans.begin(),ans.end());
return ans;
}
};
实际运行效果
我对比了按序列大小遍历、一元二次求根、滑动窗口三个方法，发现按序列大小遍历果然是最快的方法。但是之前认为一元二次求根比滑动窗口快却是错的，目前还没弄清楚为什么，后续会继续探究，欢迎交流。
对照代码：
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cmath>
using namespace std;
class Solution1 {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int> > ans;
for(int n=2;n+(n*n-n)/2<=sum;n+=1){
int a,b;
if(n%2==0 && (sum+n/2)%n == 0 || n&1 && sum%n == 0){
a = sum/n - (n-1)/2;
b = a+n-1;
vector<int> temp;
for(int i=a;i<=b;i++){
temp.push_back(i);
}
ans.push_back(temp);
}
}
reverse(ans.begin(),ans.end());
return ans;
}
};
class Solution2 {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int> > ans;
for(int a=1;a<=sum/2;a++){
double x = -1.0/2 + sqrt(1.0/4+4*(2*sum+a*a-a))/2;
int b = round(x);
if(b*b - a*a + a + b == 2*sum){
vector<int> temp;
for(int i=a;i<=b;i++){
temp.push_back(i);
}
ans.push_back(temp);
}
}
return ans;
}
};
class Solution3 {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
//子序列和的最大值
int End=sum/2+1;
int left=1;
int right=1;
int CurSum=1;
vector<vector<int> >res;
while(left<=End-1&&right<=End)
{
if(CurSum==sum)
{
GetVector(res,left,right);
right++;
CurSum-=left;
left++;
CurSum+=right;
}
else if(CurSum<sum)//增加右边界
{
right++;
CurSum+=right;
}
else
{
CurSum-=left;
left++;
}
}
return res;
}
void GetVector(vector<vector<int> >&res,int left,int right)
{
if(left==right)
{
return ;
}
vector<int>V;
for(int i=left;i<=right;i++)
{
V.push_back(i);
}
res.push_back(V);
}
};
int main(){
Solution1 s1 = Solution1();
Solution2 s2 = Solution2();
Solution3 s3 = Solution3();
vector<vector<int> > res;
time_t first,second;
first = time(NULL);
for (int i=0;i<10000;i++)
res = s1.FindContinuousSequence(100000);
second = time(NULL);
printf("s1(按序列大小遍历): %f seconds\n", difftime(second, first));
for(int i=0;i<res.size();i++){
for(int j=0;j<res.size();j++)
cout<<res[i][j]<<' ';
cout<<endl;
}
first = time(NULL);
for (int i=0;i<10000;i++)
res = s2.FindContinuousSequence(100000);
second = time(NULL);
printf("s2(一元二次求根): %f seconds\n", difftime(second, first));
for(int i=0;i<res.size();i++){
for(int j=0;j<res.size();j++)
cout<<res[i][j]<<' ';
cout<<endl;
}
first = time(NULL);
for (int i=0;i<10000;i++)
res = s3.FindContinuousSequence(100000);
second = time(NULL);
printf("s3(滑动窗口): %f seconds\n", difftime(second, first));
for(int i=0;i<res.size();i++){
for(int j=0;j<res.size();j++)
cout<<res[i][j]<<' ';
cout<<endl;
}
return 0;
}
对照结果：
s1(按序列大小遍历): 0.000000 seconds
153 154 155 156 157
738 739 740 741 742
1531 1532 1533 1534 1535
3988 3989 3990 3991 3992
19998 19999 20000 20001 20002
s2(一元二次求根): 5.000000 seconds
153 154 155 156 157
738 739 740 741 742
1531 1532 1533 1534 1535
3988 3989 3990 3991 3992
19998 19999 20000 20001 20002
s3(滑动窗口): 3.000000 seconds
153 154 155 156 157
738 739 740 741 742
1531 1532 1533 1534 1535
3988 3989 3990 3991 3992
19998 19999 20000 20001 20002
