双指针算法

引例：

给定一个有序数组[1, 4, 5, 7, 9]，试找出其中两个数使其和为12.

直观解法——O(n ^ 2)

• 最容易想到的解法就是，定义一个i，一个j，对这个数组进行二重循环
• 这种解法看起来用了两个指针，实际上只能算是暴力法

改进解法——O(n)

1. 定义一个i，一个j的，i指向第一个元素，j指向最后一个元素

2. 看i + j的值

• 如果小于目标值12，则说明值不足，根据有序数组，肯定不能将j向左移动，故应当将i向右移动
• 如果大于目标值12，则说明值超了，根据有序数组，肯定不能将i向右移动，故应当将j向左移动

3. 重复步骤2

可用双指针法求解的题目

• 344.反转字符串
• 27.移除元素
• 125.验证回文串
• 287.寻找重复数