视频讲解: https://www.bilibili.com/video/BV1CA411u7ZJ?from=search&seid=9638486758553186769
文章讲解: https://www.papamelon.com/post/g2WsVbQehep8OVtpSSNt9DOzbVExYuXZ
双指针算法的 ”套路“
两个指针各有一个初始位置
两个指针各有一个移动方向
移动停止的条件:其中一个指针到底了,两个指针相遇了,找到答案了 …
难点 (证明)
证明两个指针都不需要回退
常常利用单调性证明
例题:leecode
1. 两数之和
15. 三数之和
16. 最接近的三数之和
26. 删除排序数组中的重复项
1004. 最大连续1的个数 III
88. 合并两个有序数组
392. 判断子序列
模型:
向中间逼近模型
前后指针同向移动
与 uniue 算法同理(C++ STL algorithm)
滑动窗口模型
归并排序模型