刷过LeetCode的人,八成见过这道题:有序数组里找两数之和。有人暴力遍历O(n²),有人哈希表O(n)空间,但最优解其实藏在一个古老技巧里——双指针,时间O(n)空间O(1)。

从两头往中间夹

数组有序是前提。左指针l=0,右指针r=length-1,求和判断:等于目标直接返回,小于目标左指针右移(需要更大值),大于目标右指针左移(需要更小值)。

代码极简,核心就4行:

while(l

为什么很多人想不到?

惯性思维从左到右遍历,却忽略了"有序"这个关键条件。双指针的本质是利用单调性,把O(n²)的配对搜索压缩成O(n)的线性扫描。三数之和、盛最多水的容器、接雨水……经典题全是这套路的变体

下次看到"有序数组",先问自己:两头夹能不能做?