Two Pointers 双指针简介

Two Pointers,顾名思义:双指针。虽然它叫“双指针”,但和c/c++中的指针关系并不大。双指针思想本质上是对序列的两个不同的坐标(i,j)进行扫描,并减少时间复杂度。归并排序和快速排序都是利用了two pointers思想。

Two Pointers 双指针思想的应用

下面来看两个问题来了解two pointers:

问题一:

给定一个正整数M和正整数递增序列,求序列中两个不同的元素a,b,它们相加后恰好等于M。

这个题可以用简单的枚举,循环嵌套,其时间复杂度为O(n2),代码略。这在n为105时是不能承受的。
之所以时间复杂度高,是因为这个枚举做了很多不必要的工作,比如,在i+j的元素等于M时,再向前枚举就没有意义了,因为之后的i+j元素之和必然大于M。
事实上,如果我们仔细思考就会发现,i和j的枚举是互相牵制的。这点可以给优化带来很大空间。下面我们来利用two pointers思想来解决一下这个问题:
令i,j分别指向序列中的第一个元素和最后一个元素,以i>=j为终止条件,让i递增,j递减,然后会出现三种情况:

  • a[i]+a[j]==M,此时找出一个解这时,只有i++,j–时才有可能找到其他解;
  • a[i]+a[j]>M,此时,只有j–才能找到其他解。
  • a[i]+a[j]<M,此时,只有i++才能找到其他解。

综合以上三种情况,可以很容易写出代码:

问题二:序列合并问题。

假设有两个递增序列A和B,要求将它们合并为一个递增序列C。

根据two pointers思想,设置两个下标i和j,分别指向序列A的第一个元素和序列B的第一个元素,然后根据A[i]与B[j]的大小来决定将哪个元素放入C。下面来看三种情况:

  • 若A[i]<B[j],则应将A[i]放入C,i++;
  • 若A[i]>B[j],则应将B[j]放入C,j++;
  • 若相等,则任选1,2放。

将上述操作循环直到i,j有一个到了末位为止,此时将另一个序列全部放入C中。

标签: none

[站长收徒]-[Java架构师学习指导]-[最后一次]


添加新评论