【leetcode】20. 序列-和为s的连续正数序列

发表于 更新于 分类于 阅读次数： 本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
难易程度：easy

示例 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

分析

本题方法比较多，如暴力遍历，双指针法等，这里只介绍利用数学公式来求解的方法。
本题本质上是序列求和问题，此类问题的一个经典问题就是求1,...,100这100个数之和。当年高斯使用的方法就是(1+100)*100/2。

设s < x 且s,...,x这(x - s + 1)个连续整数之和为target。那么，有(s + x)*(x -s + 1) == 2 * target,即存在一元二次方程:
x^2 + x + s*(1-s) - 2*target = 0。
根据韦达定理解得：
x = (sqrt(1-4(s*(1-s) - 2*target)) - 1) / 2
最终本题转变成有多少个[s, x]区间的问题，即枚举s的情况下求解一元二次方程:x^2 + x + s*(1-s) - 2*target = 0 整数正值的问题。

时间复杂度：O(N)，由于枚举以后只需要 O(1)的时间判断，所以时间复杂度为枚举起点的复杂度O(target/2) 。
空间复杂度：O(1) ，除了答案数组只需要常数的空间存放若干变量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>> res;
        // 题中要求至少含有两个数，所以s最大为target-1
        for (int s = 1; s <= target / 2; s++) {
            // 主要这里s*(1-s)可能超过MAX_INT，因此同乘以1ll来提升类型，下同
            long long d = 1 - 4*(1ll * s*(1 - s) - 2 * target);
            if (d < 0) {
                continue;
            }
            int sqrt_d = (int)sqrt(d);
            if (1ll * sqrt_d * sqrt_d == d && (sqrt_d - 1) % 2 == 0) {
                vector<int> tmp;
                for (int i = s; i <= (sqrt_d - 1) / 2; i++) {
                    tmp.push_back(i);
                }
                res.push_back(tmp);
            }
        }
        return res;
    }
};