一个算法技巧，把O(n²)干成O(n)

面试官最爱考的数组题，90%的人第一反应是嵌套循环。但有人用两行代码就把时间复杂度砍了一半——这不是魔法，是双指针（Two Pointers）。

一张图看懂核心套路

双指针的本质很简单：不用一个索引遍历，而是用两个。

它们从数组两端出发，或者一快一慢前进。每次移动都基于当前状态做"聪明决策"，跳过大量无效计算。

原文给了三个经典场景，我们逐层拆解。

场景一：有序数组找两数之和

传统思路：两层循环，穷举所有组合。时间复杂度O(n²)。

双指针解法：

左指针从头，右指针从尾。两数相加，和太小则左移，和太大则右移。

代码只有8行。因为数组有序，每次移动都能确定排除掉一批不可能的组合。

最坏情况？两个指针相遇，遍历一遍。O(n)。

场景二：原地去重

这题更隐蔽。快慢指针：readIndex（读指针）扫描新元素，writeIndex（写指针）只在发现新值时才移动。

数组被复用为结果容器，空间复杂度O(1)。

关键洞察：有序数组中，重复元素一定相邻。不需要哈希表，指针比较就够了。

场景三：盛最多水的容器

LeetCode经典题。面积 = 底 × 高，底是左右距离，高是两板中的矮板。

双指针从两端收缩。哪边矮，哪边往中间走——因为移动高的那边，底变小、高不变，面积只会更小。

每次移动都基于"当前短板"做决策，全局最优在局部比较中自然浮现。

为什么它能这么快？

嵌套循环的问题是"暴力"：检查所有可能性，不管有没有意义。

双指针的狡猾在于利用数组的隐藏结构——有序性、单调性、对称性。用一次比较的信息量，剪掉一大片搜索空间。

不是算法变快了，是干的活变少了。

你的代码库该更新什么

三个模板覆盖80%面试场景：

• 对撞指针（两端向中间）：有序数组求和、判断回文、三数之和

• 快慢指针（同向不同速）：去重、判环、找中点

• 滑动窗口（动态边界）：子串问题、长度可变区间

原文只演示了前两种，但核心思想一致：用空间换时间太老套了，用信息换时间才是新思路。

数据收束

三个例子，时间复杂度统一从O(n²)降到O(n)。空间复杂度全是O(1)。

代码行数？twoSumSorted 8行，removeDuplicates 7行，maxArea 9行。

下次写嵌套循环前，先问自己一句：这数组有没有我没利用的结构？