尺取法

尺取法又叫双指针（two pointers）是竞赛中常用的优化基技巧，用来解决区间问题，操作简单。如果是单调区间也常用二分法

需要操作两个变量，可以用两个下标（指针）i，j 扫描区间。有二重循环，复杂度为O(n2)

for(int i=0;i<n;i++)
    for(int j=n-1;j>=0;j--)
        {
        }    

实际上尺取法就是把二重循环变为一个循环，在这个循环中同时处理i,j，时间复杂都也从O(n2)变为O(n)

int i=0;
int j=n-1;
while(i<j)
{
    .....i++;
    .....j--;

}
//用for实现
for(int i=0;j=n-1;i<j;i--;j++)
{
}

在扫描方式中有两种扫描方式

(1)反向扫描：i和j反向相同，i从头到尾，j从尾到头。在中将相会。

(2)同向扫描。又称快慢指针。都是从头到尾，速度不同。