双指针优化
双指针降维优化双重循环,根据某种单调性省去双重循环中多余计算的部分,以此达到O(n)时间复杂度
-
左右指针(一左一右相向或背向移动)————找两个元素匹配
例如:i为左边一个数,j为右边一个数,起始i=1,j=n,相向移动
-
快慢指针(一快一慢同向移动)————维护一个子区间
例如:i为区间左边界,j为区间右边界,起始i=j=1,一起右向移动,循环结束条件为j<=n
1. AcWing 799. 最长连续不重复子串
-
快慢双指针:
第一:用一个bool数组标记是否在维护区间的内部
第二:for循环从左往右依次枚举每一个j(右端点),j能加入则直接加入区间,j不能加入则i(左端点)右移缩小区间直到j能加入,此时[i,j]为j的最长无重复区间,因为i再右移区间长度一定会变小,i再左移一定会引入重复数字
总共时间复杂度为:O(n) -
点击查看代码
2. AcWing 800. 数组元素的目标和
-
两数组的双指针:
第一:i,j分别指向a,b数组,for循环枚举每一个i(起始:i=1,j=m)
第二:因为a,b数组都为升序,对于每一个i,while(a[i]+b[j]>x)则j不断左移,因为j右移的话a[i]+b[j]会更大,退出while循环后a[i]+b[j]等于x则直接输出,小于x则说明对于当前的i不存在a[i]+b[j]等于x,i++进入下一轮循环
总共时间复杂度为:O(n) -
点击查看代码
3. AcWing 2816. 判断子序列
-
两数组双指针:
第一:i,j分别指向a,b数组(起始:i=1,j=1)
第二:因为要求判断a数组是否为b数组的子序(原有次序排列),所有a[i]和b[j]相同则i,j均右移一位,不同则j右移一位即可,直达遍历完所有a中的数
总共时间复杂度为:O(n) -
点击查看代码
4. AcWing 1238. 日志统计
-
快慢双指针:
第一:先将所有“日志”按时间升序排序(起始:i=1,j=1)
第二:枚举每一个j(右端点),对于每一个j,while(i到j时间长度超过d)i右移,退出while循环后的[i,j]区间为合法的最长区间,统计是否有热度超过k的日志存下来即可,然后j++进入下一轮循环
总共时间复杂度为:O(nlogn) -
点击查看代码
5. AcWing 4405. 统计子矩阵
-
快慢双指针+列方向前缀和:
第一:对二维数组只进行列方向上的前缀和处理
第二:双重循环枚举矩形上边界i和下边界j的所有可能
第三:在双重循环内(i,j确定下),快慢双指针统计出所有矩形的区间和不大于k的个数:一重循环枚举所有r(右边界)(起始:l=1,r=1) 对于每一个r,while(l和r的矩形之和>k时)则l不断右移,因为左移只会更大 退出while循环后l和r的矩形之和<=k,则j-r+1则是矩形之和<=k的个数,j++进入下一轮循环
总共时间复杂度为:O(n^3)
-
点击查看代码