双指针上课笔记

![EL1{)B}5WVSJ_Z{M)}M}YP.pngB}5WVSJ_Z[{M)}M}YP.png)

上图表示两种双指针的类型： 1. 双指针一般是有两个下标的，可以像归并排序里面的合并两个数组里面的每一个序列都有一个指针。 2. 也可以两个指针都在一个序列上。

一般可以用双指针的题目，可以先写一个两重 for 循环的暴力写法，时间复杂度是 O(n^2) 的。可以通过双指针来优化达到 O(n) 的做法的。上图是一个优化的模板。 i 和 j 下标都是同向的走，时间复杂度可能是 2n，3n，，但是都是 O(n)。

![49C]Q9_UFWL2UR[69I5QG0.png


题目大概的意思是：输入一段字符串，第一个位置不是空格，每一个单词之间只有一个空格。要求每一行输出一个单词。 上面是一个简单的双指针的应用题，先简单理解一下双指针。

![]PH%KUTG5WNQ}5}LIMUOJ.png](https://cdn.acwing.com/media/article/image/2022/04/10/182747_f1657a03b8-]PH%KUTG5WNQ}5}LIMUOJ.png)

上面的一个题目是上课讲的模板题，i 在后面（i > j）,S 数组用来记录每一个数出现的次数。i 向后移动，移动之前 S[q[i]]++ 再判断 S[q[i]]是否出现过两次（S[q[i]] > 1）,如果出现过两次，那么就会进入while 循环，j 就要向后移动了（最终 j 移动到 i 的位置就跳出while 循环，因为 j 向后移动了，所以要把 j 位置的数出现的次数减掉（S[q[j]]–））。

![7QGY9GT5_3L66NG[1]]8GW.png](https://cdn.acwing.com/media/article/image/2022/04/10/182747_ff7b6ab7b8-7QGY9GT5_3L66NG[1]]8GW.png)

O(n^2) 变成 O(n) 就是双指针的牛逼之处。