题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出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 };