剑指offer-57-2
剑指 Offer 57 - II. 和为s的连续正数序列
输入一个正整数 target
,输出所有和为 target
的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
示例:
1 | 输入:target = 9 |
解法
方法一:暴力法
1 | class Solution: |
方法二:暴力+数学优化
方法一枚举每个正整数为起点,从起点开始累积 sum 和判断是否等于 $target$。注意到,如果我们知道起点 $x$ 和终点 $y$,那么 $x$ 累积到 $y$ 的和由 求和公式可知为:
$$
\frac{(x+y)\times (y-x+1)}{2}
$$
则问题转为,是否存在一个正整数 $y$,满足等式:
$$
\frac{(x+y)\times (y-x+1)}{2} = target
$$
转化后变为:
$$
y^2 + y - x^2 +x - 2\times target = 0
$$
这是关于 $y$ 的一元二次方程,其中 $a=1,b=1,c=-x^2+x-2\times target$ 直接套用求根公式解得 $y$,判断是否整数解需要满足两个条件:
- 判别式 $b^2-4ac$ 开根号需为整数
- 最后的求根公式的分子需要为偶数,因为分母为 2
1 | class Solution: |
方法三:双指针
用两个指针 $l,r$ 表示当前枚举到的以 $l$ 为起点到 $r$ 的区间,$sum$ 表示 $[l,r]$ 的区间和,由求和公式$O(1)$求得为 $sum = \frac{(l+r) \times (r-l + 1)}{2}$ ,起始 $l=1,r=2$。
一共有3种情况:
- 如果 $sum < target$ 则说明指针 $r$ 还可以向右拓展使得 $sum$ 增大,此时指针 $r$ 向右移动,既 $r+=1$
- 如果 $sum > target$ 则说明以 $l$ 为起点,不存在一个 $r$,使得 $sum == target$,此时要枚举下一个起点,指针 $l$ 向右移动,既 $l+=1$
- 如果 $sum == target$,则说明找到了合法解 $[l,r]$ ,我们需要将 $[l,r]$ 的序列放进答案数组,且我们知道以 $l$ 为起点的合法解最多只有一个,所以枚举下一个起点,指针 $l$ 向右移动,,既 $l+=1$
1 | class Solution: |
剑指offer-57-2