关于Two pointers的个人理解

刚刚在刷题的时候接触到了一道题，题的大意是给出一个递增的数字序列，并给出一个m，要求找到a,b两个数字，且和为m，并且a<b；
在示例中，给出了三种思路，二分、hash值、以及two pointers;
最后一种并没有接触过，所以去了解了一下，发现是很值得借鉴的思路；

two pointers思想是对有序数组的优化遍历；
如果根据题目中的思想，进行两层枚举，则不可避免地会使时间复杂度到达O(n^2)级别。但是可以针对序列递增这一条进行优化；
对这个有序序列，设定两个索引坐标，一个为i，一个为j分别从队头和队尾进行向中间枚举，枚举的边界条件是i<j;
在枚举过程中，必定会出现三种情况：
在此时注意一个前提条件：i必须保持增加状态，j必须保持减小状态；
1.a+b=m，此时是我们想得到的情况，并且该情况发生时，如果i增大，j减小，则a+b可能和不变；
2.a+b>m，此时，在前提条件规范下，我们可以推断如果b减小，也就是j减小，可以预测会出现a+b=m的情况；
3.a+b<m，此时，在前提条件规范下，我们可以推断，如果a增大，也就是i增大，可能会出出现a+b=m的情况；
因此，将上述判别写成代码可以有以下结果：

while(i<j){if(a[i]+a[j]==m){i++;j--;}else if(a[i]+a[j]<m){i++;}else{j--;}}

这种方法可以看成是一种取巧的方法，但是其最大的特点是有效的减少了时间复杂度，在递增序列的前提下，循环只需要进行到i>=j时停止，所以理想状态下只需要遍历半个序列，时间复杂度只需要O(n)，所以算得上求解的一种好方法；

总结

以上是生活随笔为你收集整理的关于Two pointers的个人理解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。