双指针算法——尺取法

约 222 个字 10 行代码 预计阅读时间 1 分钟

2023 3月14日

概述

---

双指针算法是一种较为基础的枚举算法的一种（我认为），简单来说就是利用两个变量或者说指针通过一定的规则遍历整个数组（通常是一维数组），达到目的。

尺取法是一种的双指针算法，也可以看成是一种另类的滑动窗口，只不过长度可以变化。简单来说尺取就是让左右两个指针l、r中r先行，一直遍历到最初满足答案的位置，然后记录答案，再让l指针右移到刚好不满足答案的位置，这样一直遍历，最终当l指针等于数组边界时，循环结束。

尺取有很多不同写法，这里给出一种，两个while循环嵌套的写法。

while(l<len){
    while(r<len&&sum<边界条件){
        r++;
        sum进行变化;
        ans记录
    }
    l++;
    ans记录;
    sum变化；
}