常见的双指针有两种形式1. 对撞指针 2. 快慢指针对撞指针 两个指针从两端向中间移动一般用于顺序结构也称左右指针。终止条件两个指针相遇或者错开快慢指针使用两个速度不同的指针在序列结构上移动又称龟兔赛跑算法有效用于处理数组、环形链表或出现循环往复的情况。常用的实现方式慢的指针移动一位快的指针移动两位1. 移动零题目移动零思路用一个cur指针扫描整个数组另一个dest指针记录非0数序列的最后一个位置保证使 [0, dest] 的元素全部为非0元素 [dest 1, cur - 1]的元素全为02. 复写零题目复写零思路如果从前往后复写用于0写两次会导致需要被复写的数被覆盖所以选择从前往后复写先找到最后一个复写的数标记当前位置然后从数组最后开始复写3. 快乐数题目快乐数思路定义一个函数func来计算一个数每个位置上的数字的平方和此题涉及到循环使用快慢指针定义慢指针为n每次func一次快指针为func(n)每次func两次直至二者相等最后判断是否为14. 盛水最多的容器题目盛⽔最多的容器思路使用对撞指针已知指针对撞容器的宽度一定缩小且容器的高度由较低侧高度决定因此每次移动较低侧指针并更新最大容量直至两个指针相遇5. 有效三角形的个数题目有效三角形的个数思路先排序三个数先固定最大数使用对撞指针left和right若相加大于最大数则说明right与[left,right-1]所有的数都能组成三角形个数right-left个right--若相加小于最大数则说明left与[left1right]所有的数都不能组成三角形left6. 和为s的两个数题目i和为s的两个s数思路使用对撞指针left和right若相加大于sright--若相加小于sletf7. 三数之和题目三数之和思路先排序固定最大数下标为i设最大数的相反数为目标数使用对撞指针left和right若相加大于目标数right--若相加小于目标数letf若等于则为正确。去重操作当找到正确数时进行去重若left1 left则left若right-1 right则right--若i-1 i则i--。小优化当最大数小于0时不存在正确答案直接进行下一层循环8. 四数之和题目四数之和思路整体与三数之和类似多套一层循环