尺取法：顾名思义，像尺子一样取一段，借用挑战书上面的话说，尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据实际情况不断地推进区间左右端点以得出答案。之所以需要掌握这个技巧，是因为尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的

时候，所以尺取法是一种高效的枚举区间的方法，一般用于求取有一定限制的区间个数或最短的区间等等。当然任何技巧都存在其不足的地方，有些情况下尺取法不可行，无法得出正确答案。

 

使用尺取法时应清楚以下四点：

1、  什么情况下能使用尺取法?

 2、何时推进区间的端点？

3、如何推进区间的端点？

3、何时结束区间的枚举？

 

尺取法通常适用于选取区间有一定规律，或者说所选取的区间有一定的变化趋势的情况，通俗地说，在对所选取区间进行判断之后，我们可以明确如何进一步有方向地推进区间端点以求解满足条件的区间，如果已经判断了目前所选取的区间，但却无法确定所要求解的区间如何进一步

得到根据其端点得到，那么尺取法便是不可行的。首先，明确题目所需要求解的量之后，区间左右端点一般从最整个数组的起点开始，之后判断区间是否符合条件在根据实际情况变化区间的端点求解答案。

尺取法核心思路

尺取法其实也是一种模拟，是解决寻找区间和问题的一种方法。

假如有这么一个问题：给你一些数，请在这些数中找到一个区间，使得区间里每一个元素的和大于或等于给定的某个值。

不会尺取法的话，肯定就会开双重循环，枚举区间起点和终点，然后每一次都求一次和，再和给定的数作比较。

尺取法与它的思路类似，都是寻找一个区间的起点和终点。做法是:

用两个指针，最初都指向，这一组数中的第一个，然后如果这个区间的元素之和小于给定的数，就把右指针向右移，直到区间和大于等于给定的值为止。之后把左指针向右移，直到区间和等于给定的值为止，保存方案，继续操作。

假如左指针指向这些数的第一个，并且右指针指向这组数的最后一个，这种情况下的子区间元素之和仍然小于给定的数的话，那么就输出-1，表示不可能。

那么怎么求区间和呢？

当然，for一遍是可以的，但是太浪费时间了。我们可以引入一个累加器，初始值等于这组数中的第一个元素（因为最开始左指针和右指针都指向它），当右指针向右移时，累加器每次就加上右指针指向的元素的值。当左指针向右移时，累加器每次就减去左指针指向的值。

怎么实现呢？

POJ 3061
http://poj.org/problem?id=3061

https://blog.csdn.net/u012910051/article/details/52183825

POJ 3320

http://poj.org/problem?id=3320

https://blog.csdn.net/david_jett/article/details/51866314

POJ 2566

http://poj.org/problem?id=2566

https://blog.csdn.net/hnust_xiehonghao/article/details/10276929