北京
分享至
刷过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.
