双指针维护笔记

双指针维护笔记

双指针特指两个指针共同维护一个数组：
从两端分别维护，从同一端点交叉维护

从两端分别维护：

例：快速排序，（从小到大排序）

在快速排序中，我们安排了两个指针从需要排序的数组的左右两端开始向中间移动

更新方式是，当 i 指针从左向右移动，j 指针从右向左移动时，若 i 的值大于 j 的值

则交换 i j 两个指针各自指向的值，继续向中间逼近，直到 i j 相遇

从同一端点交叉维护：

例：输入 n 个单词，用空格隔开，输出每行一个单词

我们令有 i j 两个指针，一开始都指向字符串组的 char[0]

首先固定一个指针 j ，指针 i 开始向右移动

更新方式是，当 i 指针指向的值为 ‘ ‘ (空格)时，两个指针中间的char段则为第一个单词

然后将 j 同步到 i 的位置并向右移动一个单位，使得 j 指向下一个单词的首字母，继续执行 i 向右移动的操作

在每次过程中输出的操作不言而喻

复杂度解释：

双指针算法可以将时间复杂度On² 优化至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)){
		......
	}
}