【问题】小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
【思路】我们可以使用双指针来进行表示一个连续正数序列的边界,然后根据等差数列的公式:sum = (begin+end)*N/2 ,当我们求得一个正数序列的和sum后,如果sum大于目标数值,我们让begin向右移动,如果小于目标数值,则让end向右移动,最终的最终,两个指针都会指到同一位置,即目标数值,从而退出循环!当等于目标时,我们将[begin, end]中的所有数存入数组中即可!
class Solution { public: vector<vector<int> > FindContinuousSequence(int sum) { vector<vector<int>> res; vector<int> tmp; int pLow = 1, pHigh = 2; while(pHigh > pLow){ int sum_list = (pHigh + pLow)*(pHigh-pLow+1)/2; if(sum_list == sum){ for(int i = pLow;i <= pHigh;i++){ tmp.push_back(i); } res.push_back(tmp); tmp.clear(); // 将tmp清空 pLow++; } else if(sum_list < sum){ pHigh++; }else{ pLow++; } } return res; } };