题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
知识点
数组
Qiang的思路
对于这个问题，我们能够知道，对于一个递增的连续正数序列，和为S的情况只有一种。所以可以通过从 1开始遍历，将每一个正数开头的序列进行检查，如果一个序列和为S就将其保存起来。但是，这样做显然时间复杂度是非常高的，所以引入了一个辅助数组，该数组中存储的是从1（或者说0）加到当前下标的和。
对于这个辅助数组，如果我们想求从a到b的和，只需要计算b位置的值减去a-1位置的值即可，大大提高了时间效率。
下面提出在寻找过程中的几个问题：
- 我们从开始整数为1开始寻找合适的正数序列，如果找到了之后应该怎么办呢？
如果找到了，说明当前序列的开始整数对应的序列已经寻找完毕，这时候我们可以从下一个整数开始继续寻找了。
- 在寻找的过程中，对于确定的开始整数，当结束整数对应的序列和小于目标S时，显然我们需要将结束整数加1，继续往下判断。另外，如果结束整数对应的序列和大于目标S时，应该怎么办呢？
因为结束整数时从小变到大的，所以肯定不可能再将其减1。当发生这种情况时，说明这个开始整数并不存在着一个满足条件的序列，所以此时应该将开始整数+1， 而结束整数保持不变即可。
- 结束条件是什么呢？
可以发现，随着遍历的进行，序列的长度将会减少，最终长度会减少为1，此时就说明遍历结束了。
但是我并不是按照上面的描述进行代码实现的，我是首先确定一个最大的结束整数，为了简单直接取S。然后开始整数设置为1，这样我就改成当序列和大于S时将结束整数减1，当序列和小于S时，考虑是否当前开始整数不合适，如果不合适就让开始整数加1，否则让结束整数加1。当序列满足条件之后需要将开始整数加1，但是如果这样做意味着加1之后的整个序列肯定小于S，所以同时将结束整数加1。最终当开始整数不再小于结束整数时结束遍历。
# -*- coding:utf-8 -*-
class Solution:
def FindContinuousSequence(self, tsum):
# write code here
l=[0]
for i in range(1, tsum+1):
l.append(l[i-1]+i)
results=[]
left=1
right=tsum
while left<right:
if l[right]-l[left-1]==tsum:
result=[]
for i in range(left, right+1):
result.append(i)
results.append(result)
left+=1
right+=1
elif l[right]-l[left-1]>tsum:
if l[right-1]-l[left-1]<tsum:
left+=1
else:
right-=1
else:
right+=1
return results
作者原创，如需转载及其他问题请邮箱联系：lwqiang_chn@163.com。
个人网站：https://www.myqiang.top。
