题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序
题解:
第一种方法,找规律
第num开始,到num+n构成的序列和 == sum
么你会发现,则这些数全部减去(num-1)后构成序列 1,2,3,4,5,,,,n,而他们的和为n*(n+1)/2
以满足条件的序列必满足: n*(num-1) + n*(n+1)/2 == sum
第二种方法,滑动窗口
使用滑动窗口,和大了,则左指针右移,并吐出左数,和小了,则右指针右移,加上右数
1 //第一种方法,找规律 2 //第num开始,到num+n构成的序列和 == sum 3 //么你会发现,则这些数全部减去(num-1)后构成序列 1,2,3,4,5,,,,n,而他们的和为n*(n+1)/2 4 //以满足条件的序列必满足: n*(num-1) + n*(n+1)/2 == sum 5 class Solution01 { 6 public: 7 vector<vector<int> > FindContinuousSequence(int sum) { 8 vector<vector<int> >res; 9 for (int i = 1; i < sum; ++i) 10 { 11 int theta = (2 * i - 1)*(2 * i - 1) + 8 * sum; 12 int gen = sqrt(theta); 13 if (gen*gen != theta)continue; 14 int a = (1 - 2 * i) + gen; 15 if (a % 2 != 0)continue; 16 vector<int>temp; 17 for (int j = 0; j < a / 2; ++j) 18 temp.push_back(i + j); 19 res.push_back(temp); 20 } 21 return res; 22 } 23 }; 24 25 //第二种方法,滑动窗口 26 //使用滑动窗口,和大了,则左指针右移,并吐出左数,和小了,则右指针右移,加上右数 27 class Solution { 28 public: 29 vector<vector<int> > FindContinuousSequence(int sum) { 30 if (sum < 3)return{}; 31 vector<vector<int> >res; 32 int L = 1, R = 2, S = 1 + 2; 33 while (L < R && R < sum){ 34 if (S == sum){ 35 vector<int>temp; 36 for (int j = L; j <= R; ++j) 37 temp.push_back(j); 38 res.push_back(temp); 39 } 40 if (S >= sum) { 41 S -= L; 42 ++L; 43 } 44 else { 45 ++R; 46 S += R; 47 } 48 } 49 return res; 50 } 51 };