算法学习之尺取法

  昨天看了道题目，大概是说给定一个整数S，求一个长度为n的序列(所有元素均为正整数)中总和不小于S的连续子序列的长度的最小值，如果不存在，则输出0。这题的朴素思路是求出该序列所有的sum(i)，然后利用类似 高中学过的数列知识a(n)=s(n)-s(n-1)的方法，将起点s从0开始枚举，枚举限制sum[s]+S<=sum[n]，在枚举过程中，利用二分搜索找到使序列和不小于S的结尾t的最小值，这样解的时间复杂度为O(nlogn)，是不是还有更快的方法呢？这里通过阅读资料，我学到了一种名为“尺取法”的方法。这种方法就是利用两个下标(起点，终点 )的不断放缩像虫子伸缩爬行一样来卡出一个最优解。这种算法由于只需遍历一遍就可以求出答案，所以时间复杂度就是O(n)。下面给出该算法的伪代码和思路:  昨天看了道题目，大概是说给定一个整数S，求一个长度为n的序列(所有元素均为正整数)中总和不