前缀和思想解决本题

输入一个正数 S，打印出所有和为 S 的连续正数序列（至少含有两个数）。

例如输入 15，由于 1+2+3+4+5=4+5+6=7+8=15，所以结果打印出 3 个连续序列 1∼5、4∼6 和 7∼8。

输入：15

输出：[[1,2,3,4,5],[4,5,6],[7,8]]

前缀和思想

我们可以求出1~n的前缀和，此处的n = sum 是偶数? sum / 2 : (sum / 2) + 1;
原因是：当sum是奇数的时候，以本题为例15， 最后就是 7 + 8， 如果是偶数，假设是16，那么边界就是8+8
但是8+8不成立，所以边界就是8

前缀和求出来之后,假设前缀和数组是ps，我们回想如何求i~j的区间和，sum[i ~ j] = ps[j] - ps[i - 1];

那么我们只需要将sum[i ~ j] 替换成sum，就可以反推出那个连续区间的和是sum了。
即：
ps[j] = sum + ps[i - 1];

C++ 代码

class Solution {
public:
    vector<vector<int> > findContinuousSequence(int sum) {
        map<int, int> mp;
        mp[0] = 0;
        vector<vector<int>> res;
        int end = sum & 1 ? (sum >> 1) + 1 : sum >> 1;
        int ps[end + 1];
        memset(ps, 0, sizeof ps);
        for (int i = 1; i <= end; i++)
        {
            ps[i] = i + ps[i - 1];
            mp[ps[i]] = i;
        }
        for (int i = 1; i <= end; i++)
        {
            if (mp[sum + ps[i - 1]])
            {
                vector<int> item;
                for (int l = i; l <= mp[sum + ps[i - 1]]; l++) item.push_back(l);
                res.push_back(item);
            }
        }
        return res;
    }
};

// 1 3 6 10 15 21 28 36 45 55 66 78 91 105 120 

双指针算法：

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int sum)
    {
        vector<vector<int>> res;
        for (int i = 1, j = 1, s = 1; i <= sum; i++)
        {
            while (s < sum) s += ++j;
            if (s == sum && j - i > 0)
            {
                vector<int> item;
                for (int k = i; k <= j; k++) item.push_back(k);
                res.push_back(item);
            }
            s -= i;
        }
        return res;
    }
};