57和为S的连续正数序列

参考资料:

[1]renhao426的回答:
https://www.nowcoder.com/profile/4885081/codeBookDetail?submissionId=17420960

思路:

整体思路:如果总和数小,big++,使得数变大, 如果数大,small++,使得数变小,得到之后,big++

自己的解法:
class Solution {
public:
    int AddFromSmallToBig(int nNum1, int nNum2)
    {
        return (nNum1 + nNum2)*(nNum2 - nNum1 + 1) / 2;
    }

    vector<vector<int>> FindContinuousSequence(int sum)
    {

        vector<vector<int>> vecResult;
        if (sum < 3)
            return vecResult;

        int nSmall = 1, nBig = 2;
        while (nSmall < (1 + sum) / 2)
        {
            int nTmp = AddFromSmallToBig(nSmall,nBig);
            if (nTmp < sum)
                nBig++;
            else if (nTmp > sum)
                nSmall++;
            else
            {
                vector<int> vecResult1;
                vecResult1.clear();
                for (int i = nSmall; i <= nBig; i++)
                {
                    vecResult1.push_back(i);
                }
                vecResult.push_back(vecResult1);
                nBig++;
            }
        }
        return vecResult;
    }
};
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {

    //整体思路:如果总和数小,big++,使得数变大, 如果数大,small++,使得数变小
    
    int small=1;
    int big =2;
    
    //其中一个值
    vector<int> result1;
    vector<vector<int> >result;
    
    while(small<=(sum/2))//因为至少两个数
    {
        int temp = SumFromSmallToBig(small,big);
        if(temp<sum)
            big++;
        else if(temp>sum)
            small++;
        else
        {
            for(int i = small;i<=big;i++)
            {
                result1.push_back(i);
            }
            result.push_back(result1);
            result1.clear();//肯定得清空
            big++;//不然就得到一个数
        }
    }
    return result;
}

    int SumFromSmallToBig(int small, int big)
    {
        return (small+big)*(big-small+1)/2;
    }
};
标准答案:
class Solution {
public:
    //从small到big的求和
int SumFromSmallToBig(int small,int big)
{
    int sum =0;
    /*
    for(int i= small;i<=big;i++)
    {
        sum+=i;
    }
    */
    /*
    另一种求和思路。
    1+2+3+4+...+n
    n+.........+1
    (1+n)*n/2
    */
    sum = (small+big)*(big-small+1)/2;
    return sum;
}

vector<vector<int> > FindContinuousSequence(int sum) {

    //本题的思路:
    //初始化small=1,big =2;
    //small到big的序列的和大于sum,small++,小于sum,big++;
    //small要小于(1+sum)/2
    //如果等于的话,接下来是big++

    int small = 1;
    int big = 2;
    int i=0;
    vector<int> sequence;
    vector<vector<int> > sequence_set;
    while(small<(1+sum)/2)
    {
        if(SumFromSmallToBig(small,big)<sum)
            big++;
        else if(SumFromSmallToBig(small,big)>sum)
            small++;
        else if((SumFromSmallToBig(small,big) == sum))
        {
            for(i=small;i<=big;i++)
            {
                sequence.push_back(i);

            }
            sequence_set.push_back(sequence);
            sequence.clear();//要注意清空!!!
            big++;
        }
    }
    return sequence_set;//要注意return
}

};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容