43 lines
1.0 KiB
Markdown
43 lines
1.0 KiB
Markdown
---
|
||
title: leetcode-he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof
|
||
date: 2020-04-09 22:14:56
|
||
tags:
|
||
categories: leetcode
|
||
mathjax: true
|
||
---
|
||
|
||
### 面试题57 - II. 和为s的连续正数序列
|
||
|
||
[题目](https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/)
|
||
|
||
|
||
|
||
<!--more-->
|
||
|
||
|
||
|
||
又是小学奥数。由等差数列求和公式$\cfrac{(首项 + 末项)×项数}{2}$ 可知，当首项为 1 的时候项数最多，又由于是连续正整数，$n^2 < (1+n)×n < (n+1)^2 $，那最大的 $n$ 就不大于 $\sqrt{2×target} + 1$。
|
||
|
||
由小到大遍历 $n$，可以求得首项。
|
||
|
||
```python
|
||
import math
|
||
class Solution:
|
||
def findContinuousSequence(self, target: int):
|
||
n = int(math.sqrt(2 * target) + 1)
|
||
if n < 2:
|
||
return []
|
||
sum_list = []
|
||
a = 0
|
||
for i in range(2, n+1):
|
||
a = ((2 * target) / i + 1 - i) / 2
|
||
if a and not a % 1:
|
||
a = int(a)
|
||
s_ = []
|
||
for j in range(0, i):
|
||
s_.append(a + j)
|
||
sum_list.append(s_)
|
||
return sorted(sum_list)
|
||
# 60 ms 13.7 MB
|
||
```
|