题解 | #和为S的连续正数序列#
和为S的连续正数序列
https://www.nowcoder.com/practice/c451a3fd84b64cb19485dad758a55ebe
#include <cmath> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param sum int整型 * @return int整型vector<vector<>> */ vector<vector<int> > FindContinuousSequence(int sum) { // write code here double t = (-1 + sqrt(1+8* sum)) /2.0; int n = (int) t; if(n == 1) { return {}; } vector<vector<int>> res; for(int i = n;i>=2;i--) { vector<int> tem; if ((2* sum - i* (i+1)) % (2*i) == 0) { int x = (2* sum - i* (i+1)) / (2*i); cout<<x<<endl; for(int k = 1;k<=i;k++) { tem.push_back(x+k); } res.push_back(tem); } } return res; } };
设长度为n的连续整数序列x+1,x+2,...x+n的和为s, 则有
nx + n(n+1) /2 = s;
依据这个方程对n进行枚举,求x, 得出每一个符合条件的序列。