标签: 双指针

本文深入解析二分查找，从基础实现到左右边界查找，强调循环不变量和边界处理。探讨了时间复杂度O(log n)和空间复杂度O(1)的优化，以及工程实践技巧。同时，分析了三数之和问题的双指针解法及优化，并介绍了前沿研究和工业应用，例如数据库索引和版本控制。

链表反转是数据结构基础，涉及指针操作、递归思维。本文解析了双指针迭代（O(1)空间）和递归（O(n)空间）两种主流方案，对比优劣并探讨工程实践要点及进阶问题，强调生产环境优先选择迭代法。

本文探讨了反转链表问题。针对该问题，文章提供了两种解决方案：递归和双指针。递归方案的关键在于确定基本情况，而双指针方案则通过迭代改变节点指向来反转链表。文章给出了对应 TypeScript 代码示例。

本文总结了二分查找的常见写法。针对查找单个目标值、查找左侧边界、查找右侧边界三种场景，分别给出了 JavaScript 代码示例，并分析了搜索区间的选择和边界收缩的策略。此外，还展示了二分查找在“最接近的三数之和”问题中的应用。

本文介绍了KMP字符串匹配算法，旨在解决朴素匹配算法效率低下的问题。核心在于利用前缀表（next数组）记录模式串的最长相同前后缀，从而在匹配失败时快速跳转，实现O(n+m)的时间复杂度。文中详细解释了next数组的计算方法和应用。