一、双指针之左右指针相关题目
1.1 题目要求：给定一个升序排列的整数数组，找到两个数，使它们的和等于给定的数，有且仅有一个满足条件的解，返回索引。
题目分析：需要两个指针，一个指向开头，一个指向末尾，然后向中间遍历，如果指向的两个数相加正好等于target的话，直接返回两个指针的位置即可，若小于target，左指针右移一位，若大于target，右指针左移一位，以此类推直至两个指针相遇停止。
题目解答：
1 class Solution {
2 public :
3 vector < int > twoSum ( vector < int > & numbers , int target ) {
4 vector < int > res ( 2 , - 1 ) ;
5 int left = 0 , right = numbers . size ( ) - 1 ;
6 while ( left < right ) {
7 int temp = numbers [ left ] + numbers [ right ] ;
8 if ( temp > target ) {
9 right -- ;
10 } else if ( temp < target ) {
11 left ++ ;
12 } else {
13 res [ 0 ] = left + 1 ;
14 res [ 1 ] = right + 1 ;
15 return res ;
16 }
17 }
18 return res ;
19 }
20 } ;
1.2 题目要求：给定n个整数的数组nums，nums中是否有元素a，b，c，满足a + b + c = 0？ 找到数组中所有的三元组。注意：解决方案中不得包含重复的三元组。
题目分析：尝试把三数和问题转化为两数和问题：同样先对数组排序，设置三个指针i,left,right，i指针指向第一个数x，则left,right要指向数组中剩余数中的两个，并且指向的两数和为-x，从而转化为两数和问题。
题目解答：
1 class Solution {
2 public :
3 vector < vector < int > > threeSum ( vector < int > & nums ) {
4 vector < vector < int > > res ;
5 int n = nums . size ( ) ;
6 if ( n <= 2 ) return res ;
7 sort ( nums . begin ( ) , nums . end ( ) ) ;
8 for ( int i = 0 ; i < n - 2 ; i ++ ) {
9 int left = i + 1 , right = n - 1 ;
10 while ( left < right ) {
11 int temp = nums [ left ] + nums [ right ] ;
12 if ( temp > - nums [ i ] ) {
13 right -- ;
14 } else if ( temp < - nums [ i ] ) {
15 left ++ ;
16 } else {
17 vector < int > tmp { nums [ i ] , nums [ left ] , nums [ right ] } ;
18 res . push_back ( tmp ) ;
19 left ++ ;
20 right -- ;
21 while ( left < right && nums [ left ] == nums [ left - 1 ] ) left ++ ;
22 while ( left < right && nums [ right ] == nums [ right + 1 ] ) right -- ;
23 }
24 }
25 while ( i + 1 < n - 2 && nums [ i ] == nums [ i + 1 ] ) i ++ ;
26 }
27 return res ;
28 }
29 } ;
1.3 题目要求：这道题让我们求最接近给定值的三数之和。
题目分析：在上一道的Sum 基础上又增加了些许难度，那么这道题让我们返回这个最接近于给定值的值，即我们要保证当前三数和跟给定值之间的差的绝对值最小，所以我们需要定义一个变量small用来记录差的绝对值。
题目解答：
1 class Solution {
2 public :
3 int threeSumClosest ( vector < int > & nums , int target ) {
4 int n = nums . size ( ) , res = INT_MIN , small = INT_MAX ;
5 sort ( nums . begin ( ) , nums . end ( ) ) ;
6 for ( int i = 0 ; i < n - 2 ; i ++ ) {
7 int left = i + 1 , right = n - 1 ;
8 while ( left < right ) {
9 int temp = nums [ left ] + nums [ right ] + nums [ i ] ;
10 if ( abs ( temp - target ) < small ) {
11 res = temp ;
12 small = abs ( temp - target ) ;
13 }
14 if ( temp > target ) {
15 right -- ;
16 } else if ( temp < target ) {
17 left ++ ;
18 } else {
19 return target ;
20 }
21 }
22 while ( i + 1 < n - 2 && nums [ i ] == nums [ i + 1 ] ) i ++ ;
23 }
24 return res ;
25 }
26 } ;
1.4 题目要求：给定n个整数的数组nums，nums中是否有元素a，b，c，d 满足a + b + c + d= target？ 找到数组中所有的四元组。注意：解决方案中不得包含重复的四元组。
题目分析：在上一道的15. 3Sum 基础上又增加了些许难度，尝试把四数和问题转化为两数和问题：同样先对数组排序，设置四个指针k,i,left,right，k指针指向第一个数，i指针指向第二个数,则left,right要指向数组中剩余数中的两个，从而转化为两数和问题。
题目解答：
1 class Solution {
2 public :
3 vector < vector < int > > fourSum ( vector < int > & nums , int target ) {
4 vector < vector < int > > res ;
5 int n = nums . size ( ) ;
6 if ( n <= 3 ) return res ;
7 sort ( nums . begin ( ) , nums . end ( ) ) ;
8 for ( int k = 0 ; k < n - 3 ; k ++ ) {
9 for ( int i = k + 1 ; i < n - 2 ; i ++ ) {
10 int left = i + 1 , right = n - 1 ;
11 int ret = target - nums [ k ] - nums [ i ] ;
12 while ( left < right ) {
13 int temp = nums [ left ] + nums [ right ] ;
14 if ( temp > ret ) {
15 right -- ;
16 } else if ( temp < ret ) {
17 left ++ ;
18 } else {
19 vector < int > tmp { nums [ k ] , nums [ i ] , nums [ left ] , nums [ right ] } ;
20 res . push_back ( tmp ) ;
21 left ++ ;
22 right -- ;
23 while ( left < right && nums [ left ] == nums [ left - 1 ] ) left ++ ;
24 while ( left < right && nums [ right ] == nums [ right + 1 ] ) right -- ;
25 }
26 }
27 while ( i + 1 < n - 2 && nums [ i ] == nums [ i + 1 ] ) i ++ ;
28 }
29 while ( k + 1 < n - 3 && nums [ k ] == nums [ k + 1 ] ) k ++ ;
30 }
31 return res ;
32 }
33 } ;
二、双指针之快慢指针
1 class Solution {
2 public :
3 int removeElement ( vector < int > & nums , int val ) {
4 int slow = 0 , fast = 0 , n = nums . size ( ) ;
5 while ( fast < n ) {
6 if ( nums [ fast ] != val ) nums [ slow ++ ] = nums [ fast ] ;
7 fast ++ ;
8 }
9 return slow ;
10 }
11 } ;
2.1 题目要求：这道题让我们移除一个数组中和给定值相同的数字，并返回新的数组的长度。
题目分析：使用slow和fast两个指针，从头部开始遍历，遍历一次fast指针前进一步，当遍历元素不满足指定的值，slow指针前进一步，这样不满足条件的整数都被移动到数组的前面。
题目解答
2.2 题目要求：这道题要我们从有序数组中去除重复项。
题目分析：这道题的解题思路是，我们使用快慢指针来记录遍历的坐标，最开始时两个指针都指向第2个数字，如果快指针指向的数等于慢指针的前1个数，则快指针向前走一步，如果不同，则两个指针都向前走一步，这样当快指针走完整个数组后，慢指针当前的坐标就是数组中不同数字的个数。
题目解答：
1 class Solution {
2 public :
3 int removeDuplicates ( vector < int > & nums ) {
4 int slow = 1 , fast = 1 , n = nums . size ( ) ;
5 if ( n <= 1 ) return n ;
6 while ( fast < n ) {
7 if ( nums [ fast ] != nums [ slow - 1 ] ) nums [ slow ++ ] = nums [ fast ] ;
8 fast ++ ;
9 }
10 return slow ;
11 }
12 } ;
2.3 题目要求：这道题要我们从有序数组中去除重复项，每个数最多重复出现2次。
题目分析：与上一道解题思路相似，我们使用快慢指针来记录遍历的坐标，最开始时两个指针都指向第3个数字，如果快指针指向的数等于慢指针的前2个数，则快指针向前走一步，如果不同，则两个指针都向前走一步，这样当快指针走完整个数组后，慢指针当前的坐标就是数组中不同数字的个数。
题目解答：
1 class Solution {
2 public :
3 int removeDuplicates ( vector < int > & nums ) {
4 int slow = 2 , fast = 2 , n = nums . size ( ) ;
5 if ( n <= 2 ) return n ;
6 while ( fast < n ) {
7 if ( nums [ fast ] != nums [ slow - 2 ] ) nums [ slow ++ ] = nums [ fast ] ;
8 fast ++ ;
9 }
10 return slow ;
11 }
12 } ;
三、双指针之后序指针相关题目：
3.1题目要求：给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1中，使得 num1 成为一个有序数组。你可以假设 nums1有足够的空间（空间大小大于或等于m + n）来保存 nums2 中的元素。在 nums1 和 nums2 中初始化的元素的数量分别是 m 和 n。
题目分析：算法思想是：由于合并后A数组的大小必定是m+n，所以从最后面开始往前赋值，先比较A和B中最后一个元素的大小，把较大的那个插入到m+n-1的位置上，再依次向前推。如果A中所有的元素都比B小，那么前m个还是A原来的内容，没有改变。如果A中的数组比B大的，当A循环完了，B中还有元素没加入A，直接用个循环把B中所有的元素覆盖到A剩下的位置。
题目解答：
1 class Solution {
2 public :
3 void merge ( vector < int > & nums1 , int m , vector < int > & nums2 , int n ) {
4 int i = m - 1 , j = n - 1 , k = m + n - 1 ;
5 while ( i >= 0 && j >= 0 ) {
6 if ( nums1 [ i ] > nums2 [ j ] ) nums1 [ k -- ] = nums1 [ i -- ] ;
7 else nums1 [ k -- ] = nums2 [ j -- ] ;
8 }
9 while ( j >= 0 ) nums1 [ k -- ] = nums2 [ j -- ] ;
10 }
11 } ;
