blog/source/_posts/2020-04-09-leetcode-he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof.md

title	date	tags	categories	mathjax
leetcode-he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof	2020-04-09 22:14:56		leetcode	true

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

题目

又是小学奥数。由等差数列求和公式\cfrac{(首项 + 末项)×项数}{2} 可知，当首项为 1 的时候项数最多，又由于是连续正整数，$n^2 < (1+n)×n < (n+1)^2 $，那最大的 n 就不大于 $\sqrt{2×target} + 1$。

由小到大遍历 $n$，可以求得首项。

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