双指针维护笔记
双指针维护笔记
双指针特指两个指针共同维护一个数组：
从两端分别维护，从同一端点交叉维护
从两端分别维护：
例：快速排序，（从小到大排序）
在快速排序中，我们安排了两个指针从需要排序的数组的左右两端开始向中间移动
更新方式是，当 i 指针从左向右移动，j 指针从右向左移动时，若 i 的值大于 j 的值
则交换 i j 两个指针各自指向的值，继续向中间逼近，直到 i j 相遇
从同一端点交叉维护：
例：输入 n 个单词，用空格隔开，输出每行一个单词
我们令有 i j 两个指针，一开始都指向字符串组的 char[0]
首先固定一个指针 j ，指针 i 开始向右移动
更新方式是，当 i 指针指向的值为 ‘ ‘ (空格)时，两个指针中间的char段则为第一个单词
然后将 j 同步到 i 的位置并向右移动一个单位，使得 j 指向下一个单词的首字母，继续执行 i 向右移动的操作
在每次过程中输出的操作不言而喻
复杂度解释：
双指针算法可以将时间复杂度On2 优化至On
可以做个简单推导：
//朴素算法
for (int i=0;i<n,i++){
for (int j=0;j<n;j++){
if (check(j,i))
......
}
}
//双指针算法
for (int i=0;i<n;i++){
while (j<=i&&check(j,i)){
......
}
}