双指针

  • 定义：双指针指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。最常见的双指针算法有两种：一种是，在一个序列里边，用两个指针维护一段区间；另一种是，在两个序列里边，一个指针指向其中一个序列，另外一个指针指向另外一个序列，来维护某种次序。

  • 模版：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    for (int i = 0, j = 0; i < n; i ++ )  // j从某一位置开始，不一定是0
    {
        while (j < i && check(i, j)) j ++ ;

        // 具体问题的逻辑
    }
    //常见问题分类：
    //    (1) 对于一个序列，用两个指针维护一段区间，比如快排的划分过程
    //    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作


  • **核心思想：*优化，将时间复杂度为O(nn)优化为O(n)

  • **思路：**在利用双指针算法解题时,考虑原问题如何用暴力算法解出,观察是否可构成单调性,若可以,就可采用双指针算法对暴力算法进行优化.

二分

  • 模版

    1
    2
    3
    4
    5
    6
    7
    8
    //输出l相当于找最大值，输出r相当于找最小值
    int l = 0, r = n;
        while(r-l > 1) {
            int mid = (l+r)/2;
            if(a[mid] >= x) r = mid;
            else l = mid;
        }
        cout<<r<<" ";