双指针

对于一个数组，使用left，right两根指针来扫描？（或许可以这么说）或许就是广义的双指针法子。

感觉滑动窗口应该算双指针的一种特殊形式。

滑动窗口

把左右指针所形成的索引区间[left, right]可以称为一个窗口。

假设遇到一个问题：请找出符合____条件的最__区间，我们就可以维护一个滑动窗口来寻找答案。

1. 固定左指针，移动右指针，使得区间符合条件；
2. 继续移动右指针，若区间不符合条件，则移动左指针使得区间重新符合条件
3. 移动右指针直到遇到索引结束

这个方法之所以不错，是因为

• 每次只需要关注窗口内的数据
• 在更新窗口的时候可以利用已有的数据化简运算

提供一个小模板

while(right < length)
{
	if (array[right] 符合条件)
	{
		right++;
		UpdateRight();
	}
	else
	{
		UpdateLeft();
		left++;
	}
}

也有使用while收紧左侧；或者在外侧套一个循环枚举左侧等变体。

快慢指针

lower和faster指针最开始都指向首位，但是faster指针的迭代速度会快于lower指针。

用途：比如寻找链表中点 —— lower每次走一步，faster走两步。如果faster到了链表尾部，则说明lower到了链表中点