和为S的连续正序列

题目描述

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

输出描述

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

第一想法

1.确定个数
2.分奇偶

• 以100为例,最长的连续正数和序列1+...+n=100(如果有的话) n最大为根号(2*100)的左整数
• 分奇偶

能被连续正数和序列相加得到的要求是

• sum 能被奇数整除(中间一个,前后互补)sum % 2 == 1
• sum 能被偶数除,小数部分为0.5(中间一对,前后互补)sum % i != 0 && sum * 2 % i == 0

AC代码

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > vec;
        vector<int> vec0;
        int tmp, cnt;
        for(int i = sqrt(2 * sum); i > 1 ; --i){
            if(i % 2 == 1 && sum % i == 0){
                tmp = sum / i - i / 2;
                cnt = i;
                while(cnt--)
                {
                    vec0.push_back(tmp);
                    tmp++;
                }
                vec.push_back(vec0);
                vec0.clear();
            }
            if(i % 2 == 0 && sum * 2 % i == 0 && sum % i != 0){
                tmp = sum / i - (i / 2 - 1);
                cnt = i;
                while(cnt--)
                {
                    vec0.push_back(tmp);
                    tmp++;
                }
                vec.push_back(vec0);
                vec0.clear();
            }
        }
        return vec;
    }
};

AC代码改进

通过/对奇偶处理的不同结果来合并两个case

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > vec;
        vector<int> vec0;
        int tmp, cnt;
        for(int i = sqrt(2 * sum); i > 1 ; --i){
            if(i % 2 == 1 && sum % i == 0 || i % 2 == 0 && sum % i == i / 2){
                tmp = sum / i - (i - 1) / 2;
                cnt = i;
                while(cnt--)
                {
                    vec0.push_back(tmp);
                    tmp++;
                }
                vec.push_back(vec0);
                vec0.clear();
            }
        }
        return vec;
    }
};

看了讨论区

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > vec;
        vector<int> vec0;
        int sn, cnt;
        int plow = 1, phigh = 2;
        while(phigh > plow)
        {
            cnt = phigh - plow + 1;
            sn = (plow + phigh) * cnt / 2;
            if(sn == sum){
                while(cnt--){
                    vec0.push_back(phigh - cnt);
                }
                vec.push_back(vec0);
                vec0.clear();
                phigh++;
            }
            if(sn < sum)
                phigh++;
            if(sn > sum)
                plow++;
        }
        return vec;
    }
};

思路

• 使用移动窗口的办法,定指针plow和phigh,若小于sum,phigh++,若大于sum,plow++,选出其间Sn与sum相等的序列.

问题

• (sum % n) * 2 == n这个表达式即可表达除以2尾数为0.5 在n为偶数的情况下.而我的表达式是这个sum % i != 0 && sum * 2 % i == 0.它的原理是什么?
• • 余数是除数的一半,小数部分为0.5.故这样表示.