和为S的正整数数列

Dear 丶 2023-02-19 14:28 27阅读 0赞

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

我的遍历代码，从sqrt(S)到S/2的区间上找：  
时间复杂度：O(N)  
空间复杂度：O(1)

class Solution {
        
    public:
        vector<vector<int> > FindContinuousSequence(int sum) {
        
            vector<vector<int> > res;
            for(int i = int(sqrt(double(sum))); i <= sum/2; i++){
        
                vector<int> l;
                if(sum % i == 0 && (sum/i) % 2 == 1) {
        
                    for(int j = i - (sum/i)/2; j <= i + (sum/i)/2; j++) {
        
                        if(j) //正整数
                        l.push_back(j);
                    }
                    res.push_back(l);
                    continue;
                }
                if(sum % (2*i+1) == 0 && sum % (2*i+1)  == 0) {
        
                    for(int j = i - (sum/(2*i+1))+1; j <= i + (sum/(2*i+1)); j++) {
        
                        if(j) //正整数
                        l.push_back(j);
                    }
                    res.push_back(l);
                    continue;
                }
            }
            return res;
        }
    };

前缀和数组相减：  
时间复杂度：O(N^2)  
空间复杂度：O(1)

class Solution {
        
    public:
        vector<vector<int> > FindContinuousSequence(int sum) {
        
            vector<vector<int>> ret;
            int tmp = 0;
            for (int i=1; i<=sum/2; ++i) {
        
                for (int j=i; j<sum; ++j) {
        
                    tmp += j;
                    if (sum == tmp) {
        
                        vector<int> ans;
                        for (int k=i; k<=j; ++k) ans.push_back(k);
                        ret.push_back(ans);
                    }
                    else if (tmp > sum) {
        
                        // 提前剪枝
                        tmp = 0;
                        break;
                    }
                }
            }
            return ret;
        }
    };

双指针滑动窗口：  
时间复杂度：O(N)  
空间复杂度：O(1)

class Solution {
        
    public:
        vector<vector<int> > FindContinuousSequence(int sum) {
        
            vector<vector<int>> ret;
            int l = 1, r = 1;
            int tmp = 0;
            while (l <= sum / 2) {
        
                if (tmp < sum) {
        
                    tmp += r;
                    ++r;
                }
                else if (tmp > sum) {
        
                    tmp -= l;
                    ++l;
                }
                else {
        
                    vector<int> ans;
                    for (int k=l; k<r; ++k) 
                        ans.push_back(k);
                    ret.push_back(ans);
                    tmp -= l;
                    ++l;
                }
            }
            return ret;
        }
    };

神仙代码(我的方法思路的改进)：  
时间复杂度：O(sqrt(N))  
空间复杂度：O(1)

class Solution {
        
    public:
        vector<vector<int> > FindContinuousSequence(int sum) {
        
            vector<vector<int> > ans;
            for (int n = (int) sqrt((double)2 * sum); n >= 2; n--) {
        
                if ((n & 1) == 1 && sum % n == 0 || (sum % n) * 2 == n) {
        
                    vector<int> list;
                    for (int j = 0, k = (sum / n) - (n - 1) / 2; j < n; j++, k++) {
        
                        list.push_back(k);
                    }
                    ans.push_back(list);
                }
            }
            return ans;
        }
    };