双指针扫描

在leetcode中，有不少题要用到双指针扫描，大致可以分这么几类，在这里总结一下。

首先要说的是双指针有两个我们非常熟悉的应用，一个是partition，一个是binary search；一个是一块一慢双指针同向扫描，保持双指针之间和慢之前的元素满足loop invariant，一个是双指针从俩边向中间夹，每次移动一个或俩个满足移动条件的指针。

使用双指针扫描的方法常常可以使算法在线性时间。

1. 双指针两边向中间加

这个思路是一前一后两个指针同时向中间扫描，每次只移动一个指针。

Container With Most Water：https://leetcode.com/problems/container-with-most-water/

这道题一前一后两个指针，每次只移动高度小的指针，因为只有这样才有可能能使每次移动后的结果比之前更大。

 1 class Solution {
 2 public:
 3     int maxArea(vector<int>& height) {
 4         int left = 0, right = height.size() - 1;
 5         int area = 0;
 6         while(left < right) {
 7             area = max(area, min(height[left], height[right]) * (right - left));
 8             if(height[left] < height[right])
 9                 left++;
10             else
11                 right--;
12         }
13         return area;
14     }
15 };

Sort Colors：https://leetcode.com/problems/sort-colors/

这是又一道两边夹的题，但是特殊的地方是这里用到了第三个指针，但思路还是类似的，使得每个指针之间的元素保持一个loop invariant。这里的loop invarint是第一个指针之前全是0，最后一个指针之后全是2。

 1 class Solution {
 2 public:
 3     void sortColors(vector<int>& nums) {
 4         int zero = 0, two = nums.size() -1;
 5         for(int i = 0; i <= two;) {
 6             if(nums[i] == 0) {
 7                 nums[i] = nums[zero];
 8                 nums[zero] = 0;
 9                 i++;
10                 zero++;
11             }
12             else if(nums[i] == 2) {
13                 nums[i] = nums[two];
14                 nums[two] = 2;
15                 two--;
16             }
17             else {
18                 i++;
19             }
20         }
21     }
22 };

Valid Palindrome：https://leetcode.com/problems/valid-palindrome/

这道题并没有从双指针的方法中得到什么优化，只是勉强算双指针的题，归在这一类而已。

 1 class Solution {
 2 public:
 3     bool isPalindrome(string s) {
 4         if(s.length() == 0)
 5             return true;
 6         int start = 0, end = s.length() - 1;
 7         for(int i = 0; i < s.length(); i++) {
 8             if(s[i] >= 'A' && s[i] <= 'Z')
 9                 s[i] = tolower(s[i]);
10         }
11         while(start < end) {
12             while(!(s[start] >= '0' && s[start] <= '9') && !(s[start] >= 'a' && s[start] <= 'z') && start < end)
13                 start++;
14             while(!(s[end] >= '0' && s[end] <= '9') && !(s[end] >= 'a' && s[end] <= 'z') && start < end)
15                 end--;
16             if(s[start] != s[end])
17                 return false;
18             start++;
19             end--;
20         }
21         return true;
22     }
23 };

这一类题还有一种典型代表是对排序数组，求kSUM，可参考这篇博客：http://www.cnblogs.com/walcottking/p/4430871.html

2. 一快一慢双指针

1）在数组的应用

这种方法非常常用，尤其是在排序、交换元素、去重中运用最广。思路可以理解为，将原数组看成两个数组，慢指针指向结果数组，快指针指向原数组，当原数组中的数满足条件时，将原数组中的数复制到结果数组中。这样其实是用同一个数组实现两个数组的功效。

Remove Duplicates from Sorted Array：https://leetcode.com/problems/remove-duplicates-from-sorted-array/

这道题非常典型运用了上述思路。

 1 class Solution {
 2 public:
 3     int removeDuplicates(vector<int>& nums) {
 4         if(nums.size() == 0)
 5             return 0;
 6         int len = 0, runner = 1;
 7         while(runner < nums.size()) {
 8             if(nums[len] != nums[runner])
 9                 nums[++len] = nums[runner];
10             runner++;
11         }
12         return len + 1;
13     }
14 };

Remove Duplicates from Sorted Array II: https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

 1 class Solution {
 2 public:
 3     int removeDuplicates(vector<int>& nums) {
 4         if(nums.size() == 0)
 5             return 0;
 6         int len = 0, runner = 1;
 7         while(runner < nums.size()) {
 8             if(nums[len] != nums[runner] || len == 0 || nums[len - 1] != nums[len])
 9                 nums[++len] = nums[runner];
10             runner++;
11         }
12         return len + 1;
13     }
14 };

Remove Element: https://leetcode.com/problems/remove-element/

这道题也是一样的，非常典型，以后要常常回顾，记下思路。

 1 class Solution {
 2 public:
 3     int removeElement(vector<int>& nums, int val) {
 4         if(nums.size() == 0)
 5             return 0;
 6         int len = 0, runner = 0;
 7         while(runner < nums.size()) {
 8             if(nums[runner] != val)
 9                nums[len++] = nums[runner];
10             runner++;
11         }
12         return len;
13     }
14 };

还有一个应用方法我们在窗口模型相关的博文中进行详细讲解：http://www.cnblogs.com/walcottking/p/4539763.html

2) 在链表中的应用

这种方法都来源于Floyd’s cycle finding algorithm，在linked list的博文中详细讲解。