题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
解题思路
剑指offer的解法
class Solution {public:vector<int> re(int small, int big){vector<int> tmpres;for(int i=small; i<=big; i++){tmpres.push_back(i);}return tmpres;}vector<vector<int> > FindContinuousSequence(int sum) {vector<vector<int>> res;if(sum<3) return res;int small=1;int big=2;int middle = (sum+1)/2;int curSum = big+small;while(middle>small){vector<int> tmpres;if(sum==curSum){res.push_back(re(small, big));}while(sum<curSum && small<middle){curSum-=small;small++;if(sum==curSum){res.push_back(re(small, big));}}big++;curSum+=big;}return res;}};
优化一下：
class Solution {public:vector<int> re(int small, int big){vector<int> tmpres;for(int i=small; i<=big; i++){tmpres.push_back(i);}return tmpres;}vector<vector<int> > FindContinuousSequence(int sum) {vector<vector<int>> res;//if(sum<3) return res;int small=1;int big=1;int curSum = 1;while(big>=small){big++;curSum+=big;while(sum<curSum){curSum-=small;small++;}if(sum==curSum && big!=small){res.push_back(re(small, big));}}return res;}};
