双指针算法

发表于 更新于 分类于 ，
本文字数： 366

双指针算法的思路

一类是两个指针指向两个序列，用来维护两个序列的某种顺序，在归并排序中，区间合并使用的算法即是双指针算法

另一类是两个指针指向同一个序列，在快速排序中的划分的过程就是双指针算法

朴素算法（暴力）：

1
2
3
4
5
6
for (int i = 0; i < n; i++ )
    for (int j = 0; j < i; j++ )
    {
        if (check(j, i))
            //逻辑
    }

双指针：

1
2
3
4
5
6
7
8
for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(j, i))
    {
        j++;
	// 题目逻辑
    }
}

上面就是双指针算法的具体逻辑

在解题时可以将时间复杂度O(n^2)的问题优化到O(n)

入手时可以先从暴力角度分析，找出暴力做法后进行优化，寻找两个数组的单调性