刷过LeetCode的人,八成见过这道题:有序数组里找两数之和。有人暴力遍历O(n²),有人哈希表O(n)空间,但最优解其实藏在一个古老技巧里——双指针,时间O(n)空间O(1)。
从两头往中间夹
数组有序是前提。左指针l=0,右指针r=length-1,求和判断:等于目标直接返回,小于目标左指针右移(需要更大值),大于目标右指针左移(需要更小值)。
代码极简,核心就4行:
while(l为什么很多人想不到?
惯性思维从左到右遍历,却忽略了"有序"这个关键条件。双指针的本质是利用单调性,把O(n²)的配对搜索压缩成O(n)的线性扫描。三数之和、盛最多水的容器、接雨水……经典题全是这套路的变体。
下次看到"有序数组",先问自己:两头夹能不能做?
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.