题解 | #和为S的连续正数序#

题解一：暴力思路
时间复杂度:O(sumsqrt(sum))可以通过求和公式

并代入
化简至如下

所以做多累加到 次，所以时间复杂度为O(sumsqrt(sum))
空间复杂度:O(1),并未申请使用除结果以外的其他内存空间

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
    if (sum == 1)return {};
    vector<vector<int> > res;
    for (int i = 1; i < sum / 2 + 1; i++) {//从1开始遍历,做多为sum / 2
        int temp_sum = 0;
        int j = i;
        vector<int> temp_list;
        while (temp_sum < sum) {
            temp_sum += j;
            temp_list.push_back(j);
            ++j;
        }
        if (temp_sum == sum) {//累加和等于sum,得到一组解
            res.emplace_back(temp_list);//emplace_back减少一次构造函数的调用
        }
    }
    return res;
}
};

题解二： 双指针
解题思路：利用数组连续的特性，使用双指针方法。

主要思路：
1、设置两个指针left 和 right 表示一个序列的始终。
2、用 left_right_sum 表示 当前序列的和， 也就是 left_right_sum = left+(left+1)+.....+(right)
3、以left 递增的方式遍历整个序列（1 到 [(目标sum-1)/2]），则查找以当前left为起始点序列的终止点right的位置。
4、此处分为3种情况：
a.当前left_right_sum == sum , 同时递增left和right;
b.当前left_right_sum > sum , 递增left,同时重新计算left_right_sum
c. 当前left_right_sum < sum, 递增right, 同时重新计算left_right_sum
5、循环结束，返回ans;

复杂度分析：
时间复杂度分析： 由于解的稀疏性，构造子序列的时间没有跨越量级。所以，最后总的时间复杂度依然是O(n)
时间复杂度： O(N)
空间复杂度: O(1)

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
    if (sum<3) // 不满足序列大于2
    {
        return {};
    }
    int left = 1;
    int right = 2;
    int left_limit = (sum-1)/2;
        int left_right_sum = left+right;
    vector<vector<int>> ans;
    while(left<=left_limit)
    {
        if(left_right_sum==sum)
        {
            vector<int> tmp;
            for(int i = left; i<=right;++i)
                tmp.push_back(i);
            ans.push_back(tmp);
            left_right_sum +=(++right);
        }
        else if(left_right_sum > sum)
            left_right_sum -= (left++);
        else 
            left_right_sum += (++right);
    }
    return ans;
    }

};

题解三： 等差数列求和公式的使用
解题思路： 利用数组连续特性，很容易看出每个子序列都是符合等差数列的，那么序列和就是等差数列求和。
主要思路：
1. ai 表示 起始值，aj 表示终止值， 那么通过等差数列求和公式 可得 s = [(ai+aj) * (aj-ai+1)]/2;
2. (ai+aj) * (aj-ai+1) = 2 * s , 使用value 表示 (ai+aj)， dist 表示 (aj-ai+1)
3. aj = (value+dist-1)/2, ai = (value-dist+1)
4. 由 (ai+aj) * (aj-ai+1) = 2*s可知, value和dist都是小于 sqrt(2 * s)
复杂度分析：
时间复杂度： O(N)
空间复杂度： O(1)

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        if(sum<3) 
        {
            return {};
        }
        vector<vector<int>>ans;
        int s = static_cast<int>(sqrt(2*sum));
        for (int i = s;i>=2;i--)
        {
            if((2*sum)%i==0){
                int value = 2*sum/i;  //(aj+ai)
                //奇奇 偶偶 （长为奇）， 奇偶 偶奇 （长为偶）
                if(value%2==0 && i%2!=0 || value%2 !=0 && i%2 ==0)
                {
                    int aj = (value+i-1)/2;
                    int ai = (value-i+1)/2;
                    vector<int> tmp;
                    for(int j = ai;j<=aj;j++)
                        tmp.push_back(j);
                    ans.push_back(tmp);
                }
            }
        }
        return ans;
    }
};