概念

双指针，顾名思义，就是利用两个指针去遍历数组，一般来说，遍历数组采用的是单指针（index）去遍历，两个指针一般是在有序数组中使用，一个放首，一个放尾，同时向中间遍历，直到两个指针相交，完成遍历，时间复杂度也是O(n)。

使用场景

• 时间复杂度：O(n) 并且 One Pass
• 空间要求：in place
• 两数之和满足某条件
  • 先对数组排序，再采用两个指针，分别从前和后往中间遍历，front增大，tail减小，通过对条件的判断，可以在O(n)内遍历，而非使用双重循环。
• in place交换
  • 一个指针正常遍历，另一个指针去找可以用来交换的元素。

例题

1. 有序数组的 Two Sum
2. 两数平方和
3. 反转字符串中的元音字符
4. 回文字符串
5. 归并两个有序数组
6. 判断链表是否存在环
7. 最长子序列

https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E5%8F%8C%E6%8C%87%E9%92%88.md

参考文章:

算法之双指针

FROM :blog.cfyqy.com | Author:cfyqy