双指针算法

#数组类
##整体印象
此类问题一般涉及几种情形：in place 的更新数组，需要一个index记录更新之后的数组，另一个index跑遍原来的数组； 还有就是找到数组里面的N个数使得这几个数满足一定的条件（如几个数之和必须为某一个特定的数）；还有就是一类特殊的问题雨水储存问题。
这里有几个关键问题需要理解:
首先数组是否排序，根据信息论的看法或者能量守恒的原理，数组是否排序与墒有关，墒的本质就是描述事物有序程度的度量，换句话说事物越有序墒的值越低，并且本质是墒会自然的会增大在无外力干扰的状况下，也就是事物总是向着无序发展的。而怎样让事物变的有序呢，那么就需要外力能量的输入来使得墒变小或者变的有序。那么在数组是否有序的问题上，我们希望它是有序的，如果不是那么就需要花费“能量”让他的墒变小，这样复杂度O(nlogn)就上去了，这里复杂度可以看作为外作用力的体现。
其次双指针问题的本质其实是由于有两个或者多个元素有相互作用或者相关联，因此在改变其中一个元素的同时其他几个元素也需要跟着改变，因此双指针问题一般是在满足几个元素关系不变的情况之下，改变一个元素的同时，寻找其他几个元素满足现有的关系情况。

实时更新数组

例题：Remove Element
分析： 这道题有几个关键字需要注意: in place, the order of elements can be changed.所以我们可以尝试用two pointers，一个记录remove过后的数组最后一个元素位置，一个用来遍历整个数组，判断条件就是比较该元素和target的值，如果不相等就把它copy给另一个pointer.因为题目只需要求最后的数组长度，所以返回最后记录位置就可以了。
复杂度： 时间复杂度O(n)，空间复杂度O(1).

class Solution {
public:
int removeElement(int A[], int n, int elem) {
    if(A == nullptr || n == 0) return 0;
    int index = 0;
    
    for(int i = 0; i < n ; ++i){
        if(A[i] != elem){
            A[index++] = A[i];
        }
    }        
    return index;
   }
};

接下来我们看一看这道题的一个变形：
例题： Remove Duplicates from Sorted Array
分析：这道题几乎和上一题一样，这里注意数组是排序的， 关键词： in place with constant memory. 有一个地方值得注意第二个pointer的起始点应该从第二个元素开始，因为实际上第二个指针是用来比较和前一个元素的值，如果相等就skip.
复杂度： 时间复杂度O(n), 空间复杂度O(1).

class Solution {
public:
int removeDuplicates(int A[], int n) {
    if(A == nullptr || n == 0) return 0;
    int index = 0;

    for(int i = 1; i < n ; ++i){
        if(A[index] != A[i]){
            A[++index] = A[i];
        }
    }            
  return index + 1;
 }
};

下面增加了一点难度，如果同一个元素允许出现两次。
例题： ［Remove Duplicates from Sorted Array II](https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array-ii/)
分析： 首先想到的是hashtable储存每个元素的个数，仔细观察题目可以发现其实不需要hashtable，因为数组是排序的，重复的元素应该会连在一起，这样遍历的时候多加一个判断就可以解决。
复杂度： 时间复杂度O(n),空间复杂度O(1).

先看一个解法建立在上一题的基础上，其中判断了前后元素是否相等，这样保证最多只有两个相同的元素：

class Solution {
public:
int removeDuplicates(int A[], int n) {
    if(A == nullptr || n == 0) return 0;
    
    int index = 0;
    for(int i = 1; i < n ; ++i){
        if(A[index] == A[i] && (index == 0 || A[index-1] != A[index]))
            A[++index] = A[i];
            
        if(A[index] != A[i])
            A[++index] = A[i];
    }
    return index + 1;
  }
};

其实可以稍加改变，使得解法更有可扩展性，处理N个重复的元素的情形：

 class Solution {
public:
int removeDuplicates(int A[], int n) {
    if(A == nullptr || n == 0) return 0;
    if(n <= 2) return n;
    
    int index = 2;
    for(int i = 2; i < n ; ++i){
        if(A[i] != A[index - 2])
            A[index++] = A[i];
    }
    return index;
  }
};

这里直接从第三个元素开始比较，如果是允许N个重复元素，2可以改为N,代码比上个解法简洁也更具有可拓展性。

前面几道题都是删除元素，还有一类问题就是排序问题有时候也可以用Two Pointers的解法.
例题: [Sort Colors] (https://oj.leetcode.com/problems/sort-colors/)
分析：这里有三个指针，但是实际是两个在操作，一个存red的index，一个存blue的index, 然后两边往中间走。
复杂度： 时间复杂度O(n), 空间复杂度O(1).

  class Solution {
 public:
  void sortColors(int A[], int n) {
      int j = 0, k = n-1;
      int i = 0;
      while(i < k + 1){
          if(A[i] == 0){
              int t = A[j];
              A[j] = A[i];
              A[i] = t;
              j++;
              i++;
          }else if(A[i] == 2){
            int t = A[k];
            A[k] = A[i];
            A[i] = t;
            k--;
        }else{
            i++;
        }    
    }
 }
};

此外这道题还有个非常巧妙的解法，利用到了partition中的原理：

 class Solution {
public:
void sortColors(int A[], int n) {
    int j = 0; 
    int k = 0;
    int i = 0;
    for(int m = 0; m < n ; ++m){
        if(A[m] == 2){
            A[k++] = 2;
        }else if(A[m] == 1){
            A[k++] = 2;
            A[j++] = 1;
        }else if(A[m] == 0){
            A[k++] = 2;
            A[j++] = 1;
            A[i++] = 0;
        }
    }
}
};

雨水问题

此类问题表面上看跟双指针没有任何关系，但是经过仔细分析，会发现有很多共同之处。
例题： Container with Most water
分析：这道题可以先找几个数模拟一下，会发现如果想让容器储存的水多，需要左右两个数距离越远越好，并且两个数中较小的数值越大越好。首先考虑暴力解法，固定一边，然后找另一边越大越好，对每一个数都查找一下，就需要O(n^2).仔细研究发现，这道题是可以用双指针的，因为最后的结果被决定于左右两个数，那么怎么进行遍历呢，如果固定一边，永远希望找比这一边大的数，因此如果比这一边小可以skip掉。于是left 和right两边左右夹逼，遇到较小的数就skip掉直到重合。
复杂度： 时间复杂度O(n), 空间复杂度O(1).

class Solution {
public:
int maxArea(vector<int> &height) {
    if(height.size() == 0) return 0;
    
    int i = 0;
    int j = height.size() -1;
    int maxA = INT_MIN;
    
    while(i < j){
        int area = min(height[j],height[i]) * (j-i);
        maxA = max(maxA, area);
        if(height[i] < height[j]){
            i++;
        }else {
            j--;
        }
    }
    
    return maxA;
}
};

再来看一个类似的题目，这里container不止一个了。
题目： Trapping Rain Water
分析：这里也是类似，对于每个柱子需要分别寻找它的左边和右边最高的柱子，这样该柱子能容纳的面积就是min(max_left, max_right) - height.因此解法自然变成了从左往右遍历，找到每个柱子左边最大值，然后从右向左遍历找到每个柱子右边最大值。最后一次遍历计算每个柱子可以容纳的面积。
复杂度：时间复杂度O(n), 空间复杂度O(n).

   class Solution {
public:
int trap(int A[], int n) {
    if(A == nullptr || n == 0) return 0;
    vector<int> right_height(n);
    vector<int> left_height(n);
    
    int height = 0, total = 0;
    
    for(int i = 0; i < n; ++i){
        if(A[i] > height) height = A[i];
        
        right_height[i] = height;
    }
    
    height = 0;
    
    for(int i = n -1; i >= 0; --i){
        if(A[i] > height) height = A[i];
        
        left_height[i] = height;
    }
    
    for(int i = 0; i < n; ++i){
        total += min(right_height[i], left_height[i]) - A[i];
    }
    
    return total;
}
};

这道题还有一个分而治之的方法，可以先遍历一边数组找到最大值，然后在最高柱子的左边和右边分别遍历就可以计算出最后的结果。
复杂度： 时间复杂度O(n), 空间复杂度O(1).

 class Solution {
public:
int trap(int A[], int n) {
    if(A == nullptr || n == 0) return 0;
    
    int result = 0;
    int max = -1, index = 0;
    for(int i = 0; i < n ; ++i){
        if(A[i] > max){
            max = A[i];
            index = i;
        }
    }
    
    int left = -1;
    for(int i = 0; i < index; ++i){
        if(A[i] > left)
            left = A[i];
        else
            result += left - A[i];
    }
    
    int right = -1;
    for(int i = n-1; i > index; --i){
        if(A[i] > right)
            right = A[i];
        else
            result += right - A[i];
    }
    
    return result;
}
};

##求和问题
下面我们开始分析一下一系列关于元素求和的问题，这一系列问题特征如下，在一组任意排序数组中，寻找N个数使得它们的（积和差除）满足某一个条件，这里可以是它们经过一系列运算满足某一个值，或者求他们的最大值等等。处理此类问题的时候，首先看数组是否是有序的，根据之前的理论如果数组是无序的，那么需要额外的力使其有序，一般是排序或者hashtable来记录每个元素，复杂度会上升。然后在数组有序的情况下进行左右夹逼，找到满足条件的元素。

例题；Two Sum
分析： 一个经典的求和问题，首先看数组是否有序， 很遗憾，没有！因此需要排序，但是注意这样复杂度就变成O(nlgn)了，有没有更好的方法，hashtable!可以保持复杂度在O(n)又可以起到排序的效果。这里注意在循环里面的判断条件，首先看target - number[i]是否在hashtable里面存在，如果存在就输出结果，如果不存在，记录当前的数进入hashtable里面。
复杂度： 时间复杂度O(n),空间复杂度O(1).

 class Solution {
public:
vector<int> twoSum(vector<int> &numbers, int target) {
    vector<int> answer(2,0);
    unordered_map<int, int> record;
    for(int i = 0; i < numbers.size(); ++i){
        int x = numbers[i];
        if(record.find(target - x) != record.end()){
            answer[1] = i + 1;
            answer[0] = record[target - numbers[i]];
            break;
        }
        record[numbers[i]] = i + 1;
    }
    return answer;
}
};

例题： 3Sum Closest
分析：还是首先看是否数组是有序的，如果不是有序的就得排序，这道题涉及到三个元素（三体问题），原则上三体问题包含了一切三个元素及以上的问题，如果说两体问题可以通过一些技巧（如hashtable)解决的话，三体问题就是复杂度提高了一个台阶，一些普适于两体的技巧在三体问题这里行不通了。因此在这里首先要对数组排序， 此题涉及到三个元素，首先头尾各放一个元素，然后中间从第二个元素，左右夹逼，我们用一个gap来计算target和现在所有值的和之差，由于已经排好序，只要比较target和现在sum的值，如果target值较小，那么说明mid的值过小因此往中间靠拢，反之right的值过大因此向中间靠拢。就这样做两重遍历可以计算到最接近target的值，因为这道题只要找最接近的数因此没有3Sum那么限制条件多。
复杂度： 时间复杂度O(n^2),空间复杂度O(1).

 class Solution {
public:
 int threeSumClosest(vector<int> &num, int target) {
    int sum = 0;
    sort(num.begin(), num.end());
    
    int min_gap = INT_MAX;
    for(auto start = num.begin(); start != prev(num.end(), 2); ++start){
        auto mid = next(start);
        auto last = prev(num.end(), 1);
        while(mid < last){
            int sumup = *start + *mid + *last;
            int gap = abs(target -sumup);
            if(gap < min_gap){
                min_gap = gap;
                sum = sumup;
            }
            
            if(sumup < target){
                mid++;
            }else{
                last--;
            }
        }
    }
    
    return sum;
 }
};

例题：3Sum
分析：这道题是标准的求和问题，方法与前面类似，但是要注意重复数的出现也就是while(b < c)里面不断夹逼如果出现近邻的元素相同的情况，需要一个while语句来移动,这样得到的最后数组一定没有重复数。还有就是a的重复情况也需要考虑。
复杂度：时间复杂度O(n^2), 空间复杂度O(1).

Solution {
 public:
vector<vector<int> > threeSum(vector<int> &num) {
    vector<vector<int> > result;
    if(num.size() < 3) return result;
    sort(num.begin(), num.end());
    const int target = 0;
    
    for(auto a = 0; a < num.size()-2; ++a){
        if( a > 0 && num[a] == num[a-1]) continue;
        auto b = a + 1;
        auto c = num.size() - 1;
        
        while(b < c){
            if(num[a] + num[b] + num[c] < target){
                do{b++;}while(b < c&& num[b] == num[b-1]);
            }else if (num[a] + num[b] + num[c] > target){
                do{c--;}while(b < c && num[c] == num[c+1]);
            }else{
                result.push_back({num[a], num[b],num[c]});
                do{b++;} while(b < c && num[b] == num[b-1]);
                do{c--;} while(b < c && num[c] == num[c+1]);
            }
        }            
    }     
    return result;
    
}
};

例题： 4Sum
分析：如果使用上面类似的方法复杂度达到了O(N^3),有没有更省时间的方法呢？想到一共是四个数之和，自然想到可不可以两两配对，这样把问题可以简化为2Sum. 这里我们使用multimap来储存两个数的和，首先要弄清楚key是什么，因为不同的两个数可能有相同的和，因此key为两个数的和，value则是a pair of indexes记录两个数在数组的位置。这样遍历multimap的同时，找到另一组数使得两组数之后为target.
复杂度：时间复杂度O(N^2), 空间复杂度O(N^2).

  class Solution {
public:
vector<vector<int> > fourSum(vector<int> &num, int target) {
   vector<vector<int>> result;
   if (num.size() < 4) return result;
   sort(num.begin(), num.end());
   
   unordered_multimap<int, pair<int, int>> cache;
   for (int i = 0; i + 1 < num.size(); ++i)
       for (int j = i + 1; j < num.size(); ++j)
           cache.insert(make_pair(num[i] + num[j], make_pair(i, j)));

   for (auto i = cache.begin(); i != cache.end(); ++i) {
        int x = target - i->first;
          auto range = cache.equal_range(x);
        for (auto j = range.first; j != range.second; ++j) {
          auto a = i->second.first;
          auto b = i->second.second;
          auto c = j->second.first;
          auto d = j->second.second;
          if (a != c && a != d && b != c && b != d) {
             vector<int> vec = { num[a], num[b], num[c], num[d] };
             sort(vec.begin(), vec.end());
             result.push_back(vec);
            }
           }
        }
    sort(result.begin(), result.end());
    result.erase(unique(result.begin(), result.end()), result.end());
    return result;
   }
};