总结了 8 道经典的算法题目，重点讲解双指针技巧的应用。涵盖移动零、复写零、快乐数、盛最多水的容器、有效三角形的个数、两数之和、三数之和及四数之和。通过快慢指针、对撞指针等策略，分析时间复杂度优化方案，并提供去重处理与边界条件的注意事项。
利用双指针，将数组划分为 3 个区间：
一开始，设指针 dest = -1，cur = 0，因为非 0 区间还未存在。cur 遍历数组会有两个情况：
1.元素为零。 ++cur，将该元素纳入 零 区间。
2.元素非零。 非零区间要多一个值，则需要扩展非零区间：++dest，然后与 cur 位置值交换。
循环结束条件为：cur 遍历完数组，没有待处理区间。
同样是双指针算法，但是从前往后模拟一遍，发现复写 0 会覆盖后面的值，所以不行。
试试从后往前，举第一个示例：从最后一个复写的数字 4 开始往前：
cur 遇到 0，往前走一步，dest 走两步并且修改为 0。cur 遇到非 0，往前走一步，dest 走一步，修改为 cur 所在值。
发现可行，答案正确。那现在需要：找到最后一个复写的数：很简单，从前往后再模拟一遍，就能找到最后一个复写的数。设 cur 为 0，dest 为 -1（把 dest 当作模拟复写完的区间，cur 为 0。0 到结尾都还未处理，全都没处理，那 dest 就在 cur 的左侧，一个空间不给）。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
第 3 步很重要。因为 cur 可能遍历了很多零，导致 dest 早都复写到 size 以外了，继续复写会导致越界访问。
注意边界条件（上图）：这种情况，单独处理就行。
解法：双指针，快慢指针。
这个数字，无论最后结果是 1，还是无限循环，他们都是无限循环，不过一个是 1，一个不是 1。
那只要利用快慢指针，一直循环，指针总会相遇。判断相遇点是否为 1 就行。
怎么使用这个快慢指针？设计一个函数，返回 n 计算后的结果，然后快指针每次'走两步（运算两次）'，慢指针每次'走一步（运算一次）'，最后判断相遇的指针是否为 1。
注意一开始不要让两个指针相等，不然直接进不去循环。（理论上可以相等，但是循环逻辑得改）。
有两个解法，第一个是暴力枚举：两层 for 循环，遍历寻找 max，会超时，O(N^2)。
第二个解法：根据单调性，利用双指针解法，对撞双指针。
单调性是什么？下面解释一下。假设取 [6,2,5,4] 计算：
左右指针分别指向 6 与 4。盛水时，计算的高度按照低的算。那先固定 4，向内移动左指针。当 4 与 2（情况 1）、4 与 5 结合时 (情况 2），计算的体积 V 在右图：怎么看，都是减小的。这样我们可以直接排除一组数据，这就是根据单调性。
所以这样：区间的左和右，高度小的指针，计算出的体积最大。接着让该指针向内移动，依次算出体积，并向内移动小的指针，期间用 max 标记最大值，最终就能获取答案，并且只需要遍历一次，时间复杂度 O(N)。
首先，任意两边之和大于第三边，才能构成有效的三角形。
但是要比较 3 次，很麻烦。如果已知 a<=b<=c，那直接比较 a+b>c 就行了，较小的两边之和大于第三边，那其他两次就不用再比较。
因此，优化就是：先对数组排序，方便取较小值。
两个解法：
1.暴力枚举，3 个 for 循环，遍历所有 3 元组。但会超时。时间复杂度 O(N^3)。
这也说明了优化比较（3->1）的重要性：若先排序，再比较，那就是 NlogN + NNN。但是不优化比较，每次都比较 3 次，就是 3NN*N，明显大于前者。
2.利用单调性，使用双指针算法解决问题。
排序后，固定最大值 c，若 left+right 已经大于 c，那 left 与 right 之间的值，与 right 比较，肯定都大于 c，可减少中间不必要的比较，直接得出 (right-left) 个有效三元组。
记数后，right--，算新的三元组。
但是此时，left + right <=c，不满足，说明 left 过小，left++，继续比较。
left 和 right 重叠后，说明比较完了，开始移动 c 指针，c--。
一直重复这个过程：
这题第一眼，就是暴力枚举，先固定一个。O(N^2)。
更优解法：利用单调性，使用双指针算法。
题目给的是升序（没给就自己利用 sort 排序，核心就是利用单调性），先让指针指向首尾，依次和 target 比较：
1.大了，right--，往小了找；2.小了，left++，往大了找；3.等于，就插入进数组，直接返回，或者返回 { .... } 类型。这是 C++ 的语法，不再赘述。
上一题是两数之和，写到三数之和那大家肯定不陌生了，也是和上题一样。
首先想到的就是暴力解法，暴力枚举，效率是 N^3。
最优解法：排序利用单调性 + 左右指针。
这题就需要变一下，固定一个数字，然后在循环内进行双指针算法，就能简单拿下。了吗？
其实不然。这题的双指针算法反而是最容易想到的，难的是去掉重复三元组和边界处理的细节！
正常方法写完后，就发现，重复的三元组被计入了，并且怎么想都去除不了重复值！
有一个比较好想的方法：利用容器 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。
这题就是 3 数之和的进阶版，第七题多套一个循环就行。效率 N^3 次幂，暴力解法 N^4 次幂。
值得注意的是：sum 结果需要强转 long long int，不然可能数据溢出。
另一份参考代码：
