Two Pointers的个人理解

Two Pointers 双指针简介

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

Two Pointers 双指针思想的应用

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

问题一：

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

这个题可以用简单的枚举，循环嵌套，其时间复杂度为O(n²)，代码略。这在n为10⁵时是不能承受的。
之所以时间复杂度高，是因为这个枚举做了很多不必要的工作，比如，在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中。