双指针用法总结(草稿，可忽略)

双指针用法总结(二)，草稿，忽略

1、技巧展示

对于双指针的理解，再进行一个小小的总结。

目的：使用双指针的目的，是在于使用两个指针来协助完成一件事情，它既可以降低时间复杂度，也可以模拟滑动窗口，等等等

技巧：

①头尾双指针

解释：用两个指针分别指向头尾元素，对元素进行操作，然后更新指针的位置(一般头尾指针相遇结束)。

②双指针用于控制区间

解释：双指针在控制区间上，比如在某个区间，它的左端点不满足题目所求答案，那么此时，我们让左端点右移一位，即可达到排除非正确解的效果。

③快慢双指针

解释：举个栗子，假如有两个指针，在每个循环中fast指针走两步，slow指针走一步。或者fast指针提前走n步，然后fast和low指针一起走。

2、小试牛刀

题目①反转字符串

本题使用了技巧①，对于需要反转的字符串使用头尾指针进行元素的交换，最后返回结果。

题目②最长无重复子数组

本题使用了技巧②，在判断子数组的时候，对左右指针进行移动，并记录无重复子数组长度的最大值。

题目③判断一个链表是否为回文结构

本题使用了技巧③，用fast和slow指针来找到链表的中点位置，然后将后半部分翻转以后与前半部分进行比较，最后得到答案。

题目④接雨水问题

本题使用了技巧②，在求接水量的时候，通过left和right指针进行高度的判断，最后得出总接水量。