LeetCode 面试题57 - II. 和为s的连续正数序列

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

示例 1：

输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：

输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

限制：

1 <= target <= 10^5
链接：????

这次我没想到 双指针的写法...,但是想到了数学的方法,蜜汁脑子

如果连续的正整数序列,假设第一个数字是a,最后一个数字是a+x的话,那么序列长度就是x + 1,而根据等差数量的求和公式: (a + a + x) * (x + 1) / 2 == target
进而推出: x^2 + (2*a + 1)*x  + 2*a - 2*x + target = 0
方程有解的辨别式: b^2 - 4*a*c = 4*a^2 -4*a + 1 + 8*target
方程的根 x = ... (表达式太麻烦了,就不写了,直接带入就好了)

注意: 在 判别式中 4*a^2 可能超出int,要先转long long 再去乘

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> vect;
    typedef long long LL;
    vector<vector<int>> findContinuousSequence(int target) {
        for (int i = 1; i <= target; ++i){
            if (4 * (LL)(i)*(LL)(i) - (LL)(4*i) + 1 + 8 * target <= 0 ) continue;
            double a = i;
            double t1 = -2*a - 1 + sqrt(4*(LL)(a) * (LL)(a) - (LL)(4*a) + 8 * target + 1);
            double x = t1 * 0.5;
            if(x == int(x) && x >= 1){
                for (int j = a; j <= a + x; ++j){
                    vect.push_back(j);
                }
                ans.push_back(vect);
                vect.clear();
            }
        }
        return ans;
    }
};

最后

以上就是朴素未来为你收集整理的LeetCode 面试题57 - II. 和为s的连续正数序列的全部内容，希望文章能够帮你解决LeetCode 面试题57 - II. 和为s的连续正数序列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。