【leetcode】20. 序列-和为s的连续正数序列
题目
输入一个正整数 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 | class Solution { |