题解 | #和为S的连续正数序列# 11-1 05 前缀和 注意mp[0] = -1;

class Solution {
public:
    /*
        从1/2开始，向后退，如果恰好都等于sum 推入ret
        如果一旦大于sum 从下一个数开始计算
    */
    vector<vector<int> > FindContinuousSequence(int sum) {
        
        vector<vector<int>>ret;

        if (sum <= 2) {
            return ret;
        }


        int half = (sum + 1) / 2;
        map<int, int>mp;
        mp[0] = -1;
        
        int cnt = 0;
        for (int i = 1; i <= half; i++) {
            cnt += i;
            mp[cnt] = i;
            // 前缀和
            if (mp.find(cnt - sum) != mp.end()) {
                vector<int>vec; 
                for (int i = mp[cnt - sum] + 1; i <= mp[cnt]; i++) {
                    if (i == 0) {
                        continue;
                    }
                    vec.push_back(i);
                }
                ret.push_back(vec);
            }
        }
        return ret;
    }
};