尺取法：顧名思義，像尺子一樣取一段，借用挑戰書上面的話說，尺取法通常是對數組保存一對下標，即所選取的區間的左右端點，然后根據實際情況不斷地推進區間左右端點以得出答案。之所以需要掌握這個技巧，是因為尺取法比直接暴力枚舉區間效率高很多，尤其是數據量大的

時候，所以尺取法是一種高效的枚舉區間的方法，一般用于求取有一定限制的區間個數或最短的區間等等。當然任何技巧都存在其不足的地方，有些情況下尺取法不可行，無法得出正確答案。

?

使用尺取法時應清楚以下四點：

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

?

總結

以上是生活随笔為你收集整理的尺取法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。