剑指 Offer 57 - II. 和为 s 的连续正数序列 - 解决方案

题目描述
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

方法1：暴力法：枚举每个正整数为起点，判断以它为起点的序列和 sum 是否等于target  

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;
        vector<int> ans;
        int s=0;
        for(int i=1;i<=sum/2;i++) 
        {
           ans.clear();
            s=i;
            ans.emplace_back(i);
            for(int j=i+1;j<=(sum/2+1);j++)
            {
                ans.emplace_back(j);
                if((s+j)<sum)
                {	
                    s+=j;
                }
                else if((s+j)==sum)
                {
                    res.emplace_back(ans);
                    break;
                }
                else
                {
                    break;
                }
		    }
        }
        return res;
    }
};

方法2：滑动窗口 

/*
如果窗口中值的和小于目标值sum， 表示需要扩大窗口，j += 1

否则，如果狂口值和大于目标值sum，表示需要缩小窗口，i += 1

否则，等于目标值，存结果，i++缩小窗口，继续执行

*/ 

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int>> res;
	vector<int> ans;
	int left=1;
	int right=2;
	int s=0;
	while(left<=sum/2)
	{
		int n=right-left+1;//表示窗口的长度 
		s=(left+right)*n/2;	//窗口为奇数 (奇加奇=偶，偶加偶=偶)，sum=(left+right)/2 *n 
							//窗口为偶数 (奇加偶为奇)， sum=(left+right)*n/2 

		if(s<sum)
		{
			right++;
		}
		else if(s>sum)
		{
			left++;
		}
		else
		{
            ans.clear();
			for(int i=left;i<=right;i++)
			{
				ans.emplace_back(i);
			}
			res.emplace_back(ans);
			left++;
		}
	}
	return res;     
    }
};