尺取法
尺取法（又称为：双指针、two pointers），是算法竞赛中一个常用的优化技巧，用来解决序列的区间问题，操作简单、容易编程。
如果区间是单调的，也常常用二分法来求解，所以很多问题用尺取法和二分法都行。
尺取法的概念
什么是尺取法？为什么尺取法能优化呢？
考虑下面的应用背景：
（1）给定一个序列。有时候需要它是有序的，先排序。
（2）问题和序列的区间有关，且需要操作2个变量，可以用两个下标（指针）i、j扫描区间。
对于上面的应用，一般的做法，是用i、j分别扫描区间，有两重循环，复杂度O(n2)。以反向扫描（即i、j方向相反，后文有解释）为例，
代码是：
for(int i = 0; i < n; i++) //i从头扫到尾
for(int j = n-1; j >= 0; j--){ //j从尾扫到头
......
}
优化：
//用while实现：
int i = 0, j = n - 1;
while (i < j) { //i和j在中间相遇。这样做还能防止i、j越界
...... //满足题意的操作
i++; //i从头扫到尾
j--; //j从尾扫到头
}
//用for实现：
for (int i = 0, j = n - 1; i < j; i++, j--) {
......
}
把同向扫描的i、j指针称为“快慢指针”
把反向扫描的i、j指针称为“左右指针”
一、快慢指针的常见算法
1、判定链表中是否含有环
经典解法就是用两个指针，一个跑得快，一个跑得慢。如果不含有环，跑得快的那个指针最终会遇到 null，说明链表不含环；
如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环。
boolean hasCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) return true;
}
return false;
}
2、已知链表中含有环，返回这个环的起始位置
ListNode detectCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) break;
}
// 上面的代码类似 hasCycle 函数
slow = head;
while (slow != fast) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
可以看到，当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。
3、寻找链表的中点
类似上面的思路，我们还可以让快指针一次前进两步，慢指针一次前进一步，当快指针到达链表尽头时，慢指针就处于链表的中间位置。
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// slow 就在中间位置
return slow;
4、寻找链表的倒数第 k 个元素
我们的思路还是使用快慢指针，让快指针先走 k 步，然后快慢指针开始同速前进。这样当快指针走到链表末尾 null 时，
慢指针所在的位置就是倒数第 k 个链表节点（为了简化，假设 k 不会超过链表长度）：
ListNode slow, fast;
slow = fast = head;
while (k-- > 0)
fast = fast.next;
while (fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
二、左右指针的常用算法
左右指针在数组中实际是指两个索引值，一般初始化为 left = 0，right = nums.length - 1。
1、二分查找
前文 二分查找 有详细讲解，这里只写最简单的二分算法，旨在突出它的双指针特性：
int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = (right + left) / 2;
if(nums[mid] == target)
return mid;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid - 1;
}
return -1;
}
2、两数之和
∎问题描述
输入n ( n≤100,000)个整数，放在数组a[]中。找出其中的两个数，它们之和等于整数m(假定肯定有解)。题中所有整数都是int型。
样例输入：
21 4 5 6 13 65 32 9 23
28
样例输出：
5 23
说明：样例输入的第一行是数组a[]，第2行是m = 28。样例输出5和23，相加得28。
void find_sum(int a[], int n, int m){
sort(a, a + n); //先排序，复杂度O(nlogn)
int i = 0, j = n - 1; //i指向头，j指向尾
while (i < j){ //复杂度O(n)
int sum = a[i] + a[j];
if (sum > m) j--;
if (sum < m) i++;
if (sum == m){
cout << a[i] << " " << a[j] << endl; //打印一种情况
i++; //可能有多个答案，继续
}
}
}
3、反转数组
void reverse(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
// swap(nums[left], nums[right])
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++; right--;
}
}
4、判断回文串
给一个字符串，判断它是不是回文串。
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >> n; //n是测试用例个数
while(n--){
string s; cin >> s; //读一个字符串
bool ans = true;
int i = 0, j = s.size() - 1; //双指针
while(i < j){
if(s[i] != s[j]){
ans = false;
break;
}
i++; j--; //移动双指针
}
if(ans) cout << "yes" << endl;
else cout << "no" << endl;
}
return 0;
}