双指针算法题型总结
两端收缩
- [1-167 两数之和 II](LeetCode 167 两数之和 II.md)
- [2-15 三数之和](LeetCode 15 三数之和.md)
- [3-11 盛水最多的容器](LeetCode 11 盛水最多的容器.md)
隐形挡板
- [4-42 接雨水](LeetCode 42 接雨水 - 双指针解法.md)
- [8-31 下一个排列](LeetCode 31 下一个排列.md)
思路
双指针题常见的关键是：先定义“当前状态”，再决定“下一步向哪边移动”。 动态规划通常是“由前推后”，双指针更多是“由当前状态剪枝后继续前进”。
以 [3-11 盛水最多的容器](LeetCode 11 盛水最多的容器.md) 为例：每次都在相邻状态里选择更有机会变优的方向，这就是双指针能降复杂度的核心。