看大家都是用双指针,我来写一种其他方法吧,纯数学解法
假设从n开始,到n+k,连续k+1个数的和等于S,则有
计算得到
由n>=1得到k的范围
因此只需对1->k遍历,找到满足上述公式(整除)的k,自然可以计算出对应的开始数字n,代码如下:
class Solution {
public:
static bool compare(const vector<int>& v1, const vector<int>& v2) {
return v1[0] < v2[0];
}
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int> > vecRet;
int n = 0;
int k = (int)sqrt(sum) + 1;
while (k >= 1) {
n = 2 * sum - k * (k + 1);
if (n <= 0 || n % (2 * k + 2) != 0) {
k--;
continue;
}
n = n / (2 * k + 2);
vector<int> vecSub;
for (int i = 0; i <= k; i++) {
vecSub.push_back(n + i);
}
vecRet.push_back(vecSub);
k--;
}
sort(vecRet.begin(), vecRet.end(), compare);
return vecRet;
}
};
京公网安备 11010502036488号