【优选算法1】双指针经典算法题
1.移动零
利用双指针，将数组划分为3个区间：
一开始，设指针dest = -1，cur = 0 ，因为非0区间还未存在。cur遍历数组会有两个情况：
1.元素为零。++cur，将该元素纳入 零 区间
2.元素非零。非零区间要多一个值，则需要扩展非零区间：++dest，然后与cur位置值交换
循环结束条件为：cur遍历完数组，没有待处理区间。
2.复写零
同样是双指针算法，但是从前往后模拟一遍，发现复写0会覆盖后面的值，所以不行。
试试从后往前，举第一个示例：从最后一个复写的数字4开始往前：
cur遇到0，往前走一步，dest走两步并且修改为0。cur遇到非0，往前走一步，dest走一步，修改为cur所在值。
发现可行，答案正确。那现在需要：找到最后一个复写的数：很简单，从前往后再模拟一遍，就能找到最后一个复写的数。设cur为0，dest为-1,（把dest当作模拟复写完的区间，cur为0。0到结尾都还未处理，全都没处理，那dest就在cur的左侧，一个空间不给）
第3步很重要。因为cur可能遍历了很多零，导致dest早都复写到size以外了，继续复写会导致野访问。
注意边界条件（上图）：这种情况，单独处理就行。
3.快乐数
解法：双指针，快慢指针。
这个数字，无论最后结果是1，还是无限循环，他们都是无限循环，不过一个是1，一个不是1
那只要利用快慢指针，一直循环，指针总会相遇。判断相遇点是否为1就行。
怎么使用这个快慢指针?设计一个函数，返回n计算后的结果，然后快指针每次“走两步（运算两次）”，慢指针每次“走一步（运算一次）”，最后判断相遇的指针是否为1
注意一开始不要让两个指针相等，不然直接进不去循环。（理论上可以相等，但是循环逻辑得改）
4.盛最多水的容器
有两个解法，第一个是暴力枚举：两层for循环，遍历寻找max，会超时，O(N*N)
第二个解法：根据单调性，利用双指针解法，对撞双指针。
单调性是什么？下面解释一下。假设取 [6,2,5,4] 计算：
左右指针分别指向6与4。盛水时，计算的高度按照低的算。那先固定4，向内移动左指针。当4与2（情况1）、4与5结合时(情况2），计算的体积V在右图：怎么看，都是减小的。这样我们可以直接排除一组数据，这就是根据单调性。
所以这样：区间的左和右，高度小的指针，计算出的体积最大。接着让该指针向内移动，依次算出体积，并向内移动小的指针，期间用max标记最大值，最终就能获取答案，并且只需要遍历一次，时间复杂度O（N）.
5.有效三角形的个数
首先，任意两边之和大于第三边，才能构成有效的三角形
但是要比较3次，很麻烦。如果已知a<=b<=c，那直接比较a+b>c就行了，较小的两边之和大于第三边，那其他两次就不用再比较。
因此，优化就是：先对数组排序，方便取较小值。
两个解法：
1.暴力枚举，3个for循环，遍历所有3元组。但会超时。时间复杂度O(N*N*N)
这也说明了优化比较（3->1）的重要性：若先排序，再比较，那就是NlogN + N*N*N。但是不优化比较，每次都比较3次，就是3*N*N*N ,明显大于前者。
2.利用单调性，使用双指针算法解决问题
排序后，固定最大值c，若left+right已经大于c，那left与right之间的值，与right比较，肯定都大于c，可减少中间不必要的比较，直接得出(right-left)个有效三元组。
记数后，right--，算新的三元组
但是此时，left + right <=c ，不满足，说明left过小，left++，继续比较
left和right重叠后，说明比较完了，开始移动c指针，c--
一直重复这个过程：
6.查找总价格为目标值的两个商品
这题第一眼，就是暴力枚举，先固定一个。O(N*N)
更优解法：利用单调性，使用双指针算法
题目给的是升序（没给就自己利用sort排序，核心就是利用单调性），先让指针指向首尾，依次和target比较：
1.大了，right-- ，往小了找 2.小了，left++，往大了找 3.等于，就插入进数组，直接返回，或者返回 { .... } 类型。这是C++的语法，不赘述。
7.三数之和
上一题是两数之和，写到三数之和那大家肯定不陌生了，也是和上题一样
首先想到的就是暴力解法，暴力枚举，效率是N*N*N。
最优解法：排序利用单调性+左右指针
这题就需要变一下，固定一个数字，然后在循环内进行双指针算法，就能简单拿下。了吗？
其实不然。这题的双指针算法反而是最容易想到的，难的是
去掉重复三元组和边界处理的细节！
正常方法写完后，就发现，重复的三元组被计入了，并且怎么想都去除不了重复值！
有一个比较好想的方法：利用容器set，去掉ret中重复三元组后，再返回ret。但这样只会回去等通知！这不是一个兼顾效率和思想深度的解法。
下面提供一个新思路：
当插入一组三元组后，让left和right往内走一步。然后再先后单独用while循环比较nums
[ left ] == nums[ left - 1 ] 和 nums[ right ] == nums[ right + 1 ]，这样做是因为：若不去重，找到一组三元组后，常规做法是继续固定外层 i，然后left+，right--。但这次还需要排除重复三元组，那就是排除重复的nums[left]和nums[right]，已知这是排序后的数组，所以，向内的相邻数据就可能是重复值！所以就比较比较，如果相等，就跳过，直到不相等，跳出了重复值，继续比较内部的不同数字是否构成新三元组。
同理，外部固定的 i，也要去重。因为如果i++后还是相同值，下次循环内部的left和right重置，还是会遍历到上面跳过的值。所以 i 需要去重，去重后，i 不同，三元组也会不同。
但是，这样写完后，就发现：还是错了！ 原因其实是边界未处理：
上面的比较过程中，left持续++，可能导致left++越界了！
需要加上限制条件：left<right i 的条件就是 i < n
8.四数之和
这题就是3数之和的进阶版，第七题多套一个循环就行。效率N3次幂，暴力解法N4次幂。
最恶心的是：sum结果需要强转long long int，不然可能数据溢出。
另一份参考代码：
