当前位置: 代码迷 >> 综合 >> 面试题57:和为S的连续正整数序列
  详细解决方案

面试题57:和为S的连续正整数序列

热度:27   发布时间:2024-01-16 18:02:11.0

题意:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序,序列间按照开始数字从小到大的顺序

思路:假设这个正整数序列的长度为n,那么;

当n为奇数时,如果sum%n==0,那么这个序列肯定存在(很好理解)

当n为偶数时,如果sum%n*2==n,那么这个序列也存在

解释:

假设有四个数x1,x2,x3,x4,平均数为x;x为x取整,x = x-0.5

(x1+x4)/2=(x2+x3)/2=x,也就是x*2 = (x1+x4) = (x2+x3)

(x1+x4) - (x-x) =1;=>(x1+x4)%x =1;........................1

(x2+x3) - (x-x) =1;=>(x2+x3)%x =1;........................2

1式和2式相加,即(x1+x2+x3+x4)%n  = 2;

....

这里一共有n/2对,也就是n/2个1,所以余数是n/2;=>(x1+x2+...(xn-1)+(xn))/n = x...n/2;

也就是sum%n = n/2;

代码:

#include <iostream>
using namespace std;
#include <vector>class Solution {
public:vector<vector<int> > FindContinuousSequence(int sum) {vector<vector<int> > ans;vector<int> tmp;for (int n = sqrt(sum*2.0); n >= 2; n--){//cout << n << endl;if (n & 1 == 1 && sum % n == 0){//cout << n << "----------" << endl;tmp.clear();for (int i = 0, j = sum / n - (n - 1) / 2; i < n; i++, j++)tmp.push_back(j);ans.push_back(tmp);}else if (sum % n * 2== n  ){//cout << n << "----------" << endl;tmp.clear();for (int i = 0, j = sum / n - (n - 1) / 2; i < n; i++, j++)tmp.push_back(j);ans.push_back(tmp);}}return ans;}
};
int main()
{Solution ss;vector<vector<int>> ans = ss.FindContinuousSequence(3);cout << endl;cout << ans.size() << endl;for each (vector<int> var in ans){for each(int i in var){cout << i << '\t';}cout << '\n';}system("pause");return 0;
}

 

 

 

 

  相关解决方案