随笔档案

两个指针的作用

两个指针一般用在一个序列中。
在一个序列中处理问题时，如果只使用一个指针，可能会造成双重循环的问题，结果时间复杂度会是 O(N) 。
如果采用两个指针可以很好地解决问题，时间复杂度也可以得到改进。

采用两个指针的例子很多，这里举几个：
1.
自动文摘中，如果采用循环查找的方法，时间复杂度是幂次方。采用两个指针，分别指向文摘的开始处和结束处可以在 O(N) 的时间复杂度内找到文摘。

2.
求连续数字之和等于一给定数，例如给定数是 15 ，则结果有 1 2 3 4 5、4 5 6、7 8 三种结果。
如果采用循环的方法事件复杂度是 O(N^2)
可以采用两个指针，分别指向 small 和 big 。当 sum(small ... big) 大于给定数时，small 指针右移，当 sum 小于给定数时，big 指针右移。直到 small 是给定数的一半时。

3.
调整数组，是前半部分是某种类型的数，后半部分是某种类型的数。
比如前半部分是奇数，后半部分是偶数
前半部分是负数，后半部分是非负数
采用两个指针，分别从左右两端进行扫描，检测，如果符合条件则交换两数，直到两个指针交叉为止。

4.
求一个数组中两个数的和等于一定数。
先对数组排序
然后从数组两端用两个指针扫描，检测，直到两个指针交叉为止。

当一个指针无法很好解决问题时，应该再增添一个指针，多一个帮手。