看大家都是用双指针,我来写一种其他方法吧,纯数学解法
假设从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; } };