3.2节讲了一个很通用的方法，叫尺取法。
尺取法通常设定前后两个指针，不断地按照某种策略移动前后指针，考察前后指针所限定的区间。
例如例题3.2.1：给定长度为n的整数序列，求出总和不小于S的连续子序列的长度的最小值。按照尺取法，设定前后指针s=0,t=0,然后将s向前移动，判断t~s之间的区间是否满足要求，如果小于S，s继续移动，直到和大于等于S为止。此时将t向前移动。反复进行该过程，期间记录长度，并更新长度的最小值。复杂度为O(N)。
事实上，前后指针，或者叫双指针的方法适用于更广的问题。这里列举几个例子。
Case 1：判断数组a[0…n-1]中是否存在两个数其和为S。
Solution：先排序，然后设定首尾指针head=0, tail=n-1，两个指针向中间移动。当a[head] + a[tail] < S时，head++，否则tail--。
Case 2：单链表中，如何在O(N)时间复杂度和O(1)的空间复杂度找到倒数第k个节点？
Solution：除了先遍历一遍求得长度外，另一种有趣的方法是设定两个指针s和t，让s先向前移动k个节点，然后s和t同时移动，当s到链表尾时，t正好在倒数第k个。
Case 3：判断链表是否有环。
Solution：这是经典的面试问题了。设定两个指针，quick和slow，均初始化为链表头，quick每次移动两个节点，slow每次移动一个节点。当quick和slow相遇时，说明有环，如果指针遇到链表尾，说明无环（有环链表不会出现尾）。
Case 4：两个单链表相交成Y型，求交点，要求仅遍历一遍，空间复杂度O(1)。
Solution：这道题比较tricky。在给定的复杂度限定下，可以从一个链表头开始，将该链表所有的节点的next指针置为NULL，然后从另一个链表头开始，遍历，遇到NULL指针表示走到了交点。
（该方法破坏了链表结构，所以实践中应该不会用到这种方法，写在这里权当开拓思路了）
如果不是复杂度限定，我们有多种方法找到交点。这里我们提供几种比较容易想到的方法：方法1：先分别遍历一遍，求出两个链表的长度L1、L2（设L1 > L2），长的先移动L1-L2个节点，然后两个链表的指针同时走并进行比较，指针相等则说明是交点。
方法2：遍历其中一条链表，将该链表的所有节点地址存入map，然后遍历另一条链表，如果节点地址出现在了map中，说明这个节点是交点。
Read full article from 《挑战程序设计竞赛》读书笔记（五）尺取法 | 薛途的博客
