题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
返回值描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
示例1
输入
9
返回值
[[2,3,4],[4,5]]
思路
方法一：暴力
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int> > ans;
for(int a=1;a<sum;a++){
vector<int> temp;
for(int b=a;b<sum;b++){
if((a+b)*(b-a+1)/2 == sum){
for(int i=a;i<=b;i++){
temp.push_back(i);
}
}
}
if(!temp.empty())ans.push_back(temp);
}
return ans;
}
};
其实这道题还可以挖出很多隐含条件。比如[100]不为和为100的序列，说明
。这时根据求和公式
可以得到
。这些条件可以进一步优化答案。
方法二：滑动窗口
滑动窗口算法的思路是这样：
- 在数组中使用左右两个下标，先让
l = r = 0。此时，序列[l, r]为一个窗口。 - 先不断地增加
r扩大窗口，直到窗口中的序列可能可以在l向右滑动时符合要求（eg.sum>=9）。 - 此时，停止增加
r，转而不断增加l缩小窗口[l, r]，直到窗口中的序列不再可能符合要求（eg.sum<9）。 - 重复第 2 和第 3 步，直到
l,r达到允许范围的最大值。途中记录下满足要求的结果（eg.sum=9）。
根据之前推导的 可以确定l、r的边界。
以9为例进行示意：
1 2 3 4 5 6 7 8 9
l r | | | | 1
l | r | | | 3
l | | r | | 6
l | | | r | 10
l | | r | 9 ---- 满足
l | r 12
l r 9 ---- 满足
题解：
// [`饭带给`牛友的代码]https://www.nowcoder.com/profile/839575892
class Solution {
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&&right<=End)
/**
* 笔者备注：
* 这里判断条件
* `left<=End&&right<=End`
* 可以改为
* `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);
}
};
方法三：一元二次方程组求解
直接通过一元二次方程组求解是我目前觉得最快的方法。只需要对a进行遍历，借由a、sum求出b，再反证b的正确性即可。这里因为一元二次方程的求根公式是带根号的，会解出浮点数，计算过程存在误差，所以需要反证。
题解：
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int> > ans;
for(int a=1;a<=sum/2;a++){
vector<int> temp;
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){
for(int i=a;i<=b;i++){
temp.push_back(i);
}
}
if(!temp.empty()) ans.push_back(temp);
}
return ans;
}
};
