C++ 利用等差数列和的数学公式,复杂度O(sqrt(N))

和为S的连续正数序列

http://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe

vector<vector<int> > FindContinuousSequence(int sum) {
    int mmax = (int)sqrt(2 * sum);    // 求出可能的数列中个数做多(mmax)的情况,即:1+2+...+m = sum 的情况,此时有 m=mmax
    vector<int> one;
    vector< vector<int>> rt;
    for (int k = mmax; k >= 2; k--) {    // k:数量,保证数量 m 越多的,保存在 rt 的最前面
        if ((2 * sum - k * k + k) % (2 * k) == 0) {    
            int n = (2 * sum - k * k + k) / (2 * k);    // n: 等差数列的下限坐标
            for (int l = n; l <= n + k - 1; l++) {      // n + k -1: 等差数列的上限坐标
                one.push_back(l);
            }
            rt.push_back(one);
            one = {};    // 每次使用one 保存一种情况后,便清除其中的数据
        }
    }
    return rt;
}
全部评论

相关推荐

1 收藏 评论
分享
牛客网
牛客企业服务