双指针用法总结

双指针用法总结

1、技巧展示

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

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

技巧：

①双指针用在两个地方来解决共同目标

解释：当两个数组进行合并的时候，我们可以想到用双指针，来分别指向两个数组，然后对合并的条件进行判断，这样解决了数组合并这个共同的目标。

②双指针看作滑动窗口

解释：将双指针看作滑动窗口时，即固定左右指针之间的距离，然后将左右指针同时移动即可。

③双指针用于控制区间

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

④快慢双指针

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

⑤头尾双指针

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

2、小试牛刀

题目①合并两个有序的数组

本题使用了技巧①，在合并两个数组时，用了两个指针，来比较大小，较小的那个值放入到合并后的数组中。

题目②最小覆盖子串

本题使用了技巧③，在判断子串的时候，对左右指针进行移动，并记录能够覆盖字符串的最小值。

题目③删除链表的倒数第n个节点

本题使用了技巧④，我们让一个指针提前走n步，然后两个指针一起向前走，当提前走的指针指向为NULL时，此时即可进行删除操作。

题目④数组中相加和为0的三元组

本题使用了技巧③，在求和为0的三元组时，首先固定一个，然后另外两个用左右指针来指向，并且通过判断条件来对指针进行移动，最后得到答案。

题目⑤滑动窗口的最大值

本题使用了技巧②，将双指针看作滑动窗口，进行移动，保留窗口内的最大值。

题目⑥反转字符串

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