【剑指Offer】面试题57-2:和为s的连续正数序列

题目:输入一个正数 s,打印出所有和位 s 的连续正数序列(至少含有两个数)。例如,输入 15,由于 1+2+3+4+5=4+5+6=7+8=15,所以打印出这 3 个连续序列 1~5、4~6 和 7~8。

思路 1:穷举

最直观的思路是:穷举 1~s/2 之间的数对,验证数对中的连续正数序列和是否等于 s。这个算法的时间复杂度是 $O(n^2)$。我们需要思考更快的方法。

思路 2:左右逢源

这个思路是:定义两个指针,左指针右移能使和变小,右指针右移能使和变大;初始化左右指针为 1 和 2;使右指针右移,左右指针所指的数字的连续正数序列的和会变大,当和大于 s 时,左指针右移一位,使得和变小;当和小于 s 时,继续右移右指针,使和变大;当和等于 s 时,我们就找到了一个连续序列满足要求;直到指针超出边界。这个算法的时间复杂度是 O(n)。