I IT 面试题库
双指针有哪几种常见形态?各自适合解决什么问题?时间复杂度如何?
初级简答题算法工程师Java后端工程师双指针对撞指针快慢指针复杂度
题目
考察点:对撞指针(首尾向中)、快慢指针(同向往右,如判环/去重)、固定间距指针;理解它们把暴力 O(n^2) 降到 O(n) 的底层逻辑。
参考答案
内容深度:适中 · 无代码示例 · 来源:外部链接 · 未复核 · 79 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解
要点:
- 对撞指针(左右指针):左起右终,根据条件向中间收缩,常用于有序数组的两数之和、反转、盛水容器、回文判定。典型
while left < right 循环,每步排除无效区间,复杂度 O(n)。
- 快慢指针:两指针同方向、速度不同。快指针探路、慢指针写/标记,常用于原地去重(升序数组去重)、链表判环(Floyd 环检测)、找中点。复杂度 O(n) 且原地、O(1) 额外空间。
- 固定间距指针(滑动窗口雏形):两指针保持固定距离,随窗口整体平移,用于找定长子数组的最值。
- 为什么高效:把“枚举所有配对”的 O(n^2) 通过单调性/有序性剪枝成 O(n);前提是数组有序或对问题有单调性可利用,否则双指针不成立。
- 易错点:边界
left < right 还是 <=、left++/right-- 的触发条件、是否漏掉重复元素,都需要结合样例推演。
题目与答案就在本页;收藏、批注和错题重练在应用内