YCBlogs 数组算法题精讲：双指针查找和为 s 的两个数字（有序数组 Two Sum）
教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载本篇基于 YCBlogs 仓库 LeetCode 专栏中的 和为s的两个数字 展开讲解一道经典的数组面试题在递增排序的数组中查找两个数使它们的和恰好等于给定数字 s。读完后你将掌握双指针对撞指针法在有序数组上的完整推导逻辑、可直接运行的 Java 参考实现、逐步执行过程演示以及时间/空间复杂度的分析方法并理解它与暴力枚举、哈希表方案在取舍上的区别。01. 题目要求原题描述如下输入一个递增排序的数组和一个数字 s在数组中查找两个数使得它们的和正好是 s如果有多对数字的和等于 s输出任意一对即可。示例输入数组 {1, 2, 4, 7, 11, 15} 和数字 15。由于 4 11 15因此输出 4 和 11。这道题与无序数组上的“两数之和”最大的区别在于数组已经排好序。这个前提是整个算法能以 O(n) 时间完成的关键后面会结合分析展开。02. 问题分析为什么用双指针先明确一个朴素想法在数组中任选两个数字如果它们的和等于输入的 s就找到了答案。但难点在于“选哪两个”——如果任意两个都试一遍就是 O(n²) 的暴力枚举。核心思路与原文档的分析一致是利用有序性来控制指针的移动方向和小于 s 时我们希望两个数字的和再大一点。由于数组已排好序可以选择较小数字后面的数字——排在后面的数字更大两数之和也随之变大就有可能等于 s。于是把左指针较小数字一侧向右移动和大于 s 时对称地选择较大数字前面的数字因为排在前面的数字更小和会变小。于是把右指针较大数字一侧向左移动和等于 s 时找到答案结束。这个方法的正确性在于每一轮比较都能排除一边不可能出现答案的区间。以data[behind] data[ahead] s为例此时对于 ahead 这一列右侧的任何更大的元素与 data[behind] 配对只会更大所以data[ahead]及它右边的所有元素都不可能成为与 data[behind] 配对的答案可以放心地把右指针左移不会漏解。两个指针从两端向中间对撞最多移动 n 次就完成了全部搜索。03. 实例代码原文档给出的 Java 参考实现如下完整继承并补充了注释说明/** * 输入一个递增排序的数组和一个数字s在数组中查找两个数使得得它们的和正好是s。 * 如果有多对数字的和等于s输出任意一对即可。 * * param data 递增排序的数组 * param sum 目标和 s * return 满足条件的两个数按小、大顺序无解时返回空 List */ public static ListInteger findNumbersWithSum(int[] data, int sum) { ListInteger result new ArrayList(2); // 防御性检查数组为空或长度不足 2直接返回空结果 if (data null || data.length 2) { return result; } int ahead data.length - 1; // 右指针从最后一个元素开始 int behind 0; // 左指针从第一个元素开始 long curSum; // 统计和取 long 是防止 data[behind]data[ahead] 结果溢出 while (behind ahead) { // 左指针仍在右指针左侧才继续 curSum data[behind] data[ahead]; if (curSum sum) { result.add(data[behind]); result.add(data[ahead]); break; // 只要求任意一对找到即退出 } else if (curSum sum) { behind; // 和太小左指针右移 } else { ahead--; // 和太大右指针左移 } } return result; }实现中有几个值得注意的工程细节返回类型选ListInteger而非定长数组调用方通过判空即可区分“无解”与“有解”且天然支持“有多对时输出任意一对”的题意代码在命中后立即breakcurSum使用long类型累加两个 int 直接相加可能溢出例如两个接近Integer.MAX_VALUE的数先转为 long 再比较可以避免错误判断这是原文档注释中明确强调的防御手段循环终止条件behind ahead保证两个指针不相交、不重复取同一元素也覆盖了“恰好相邻两个元素为答案”的边界情况。04. 执行过程推演用题目示例{1, 2, 4, 7, 11, 15}、s 15走一遍完整流程可以验证每轮都只淘汰一边轮次behind 指向ahead 指向curSum与 15 比较指针动作111516大于ahead 左移211112小于behind 右移321113小于behind 右移441115等于命中返回 [4, 11]4 轮即结束。再看一个无解的情况数组{1, 2, 3, 4}、s 10。指针依次为 (1,4)→和 5 太小→右移左指针……每一步都缩小区间最终behind ahead退出循环返回空 List不会死循环也不会越界。05. 复杂度分析从源码结构看整个算法只有while (behind ahead)这一个循环每轮迭代behind和ahead中恰好有一个移动一步且两者合计最多移动 n-1 步就会相遇因此时间复杂度 O(n)最坏情况遍历约 n/2 对位置量级线性。参照仓库中 时间复杂度 笔记的方法只需关注循环执行次数最多的核心代码段即可判定空间复杂度 O(1)除结果 List至多 2 个元素外只使用了两个指针和若干临时变量不随数据规模增长属于 空间复杂度 笔记中典型的常量阶情形。06. 与其他方案的对比取舍方案时间复杂度空间复杂度是否依赖有序说明暴力双重循环O(n²)O(1)否任意两两配对直观但慢哈希表O(n)O(n)否遍历一遍记录sum - x无序数组的标准解双指针本文O(n)O(1)是有序数组下的最优解三者取舍清晰如果数组无序要么先排序再双指针排序额外引入 O(n log n)要么用哈希表以 O(n) 空间换时间如果题目像本题一样保证递增排序双指针是时间、空间都不吃亏的选择——这正是本题把“排序”写进题意的用意。07. 边界与易错点小结null 与长度 2原实现开头直接返回空 List调用方需按空集合处理避免 NPE溢出求和用long见上文若元素可能为负数或接近 int 极值这一点必须保留相等元素当数组含重复值如{3, 3, 4}、s6时双指针依然正确因为behind ahead保证取的是两个不同位置的元素多对答案题意允许任意一对代码命中即break若题目变体要求所有不重复的组合可在命中后继续behind并跳过重复值逻辑不变。08. 相关题与延伸阅读本仓库中 二维数组中查找 使用了同源思想利用行/列有序性从右上角出发每一轮剔除一行或一列本质是双指针思想在二维上的推广值得对照阅读数组的基础介绍 梳理了数组的随机访问特性与 O(1) 下标寻址原理是理解“按指针下标取值零成本”这一前提的基础时间复杂度 与 空间复杂度 两篇笔记可作为本文第 05 节分析方法的完整参考。总结本题的完整结论可以压缩为一句话在有序数组上求“两数之和”用左右双指针对撞和小于目标则右移左指针和大于目标则左移右指针O(n) 时间、O(1) 空间。其背后是可迁移的方法论——先判断数据是否有序再决定用“顺序扫描 哈希”还是“单调区间收缩 双指针”。原文档位于 leetcode/01.数组/32.和为s的两个数字.md本篇在其题目、分析与参考代码的基础上补充了逐轮推演、复杂度证明与方案对比可作为面试复习的完整版本。赞分享教程技术博客文档【免费下载链接】YCBlogs技术博客笔记大汇总包括Java基础线程并发数据结构Android技术博客等等常用设计模式常见的算法网络协议知识点部分flutter笔记还包括平时开发中遇到的bug汇总当然也在工作之余收集了大量的面试题长期更新维护并且修正持续完善……开源的文件是markdown格式的转载请注明出处谢谢项目地址https://gitcode.com/gh_mirrors/yc/YCBlogs点击查看免费下载相关推荐LeetCode-Go 题解167. Two Sum II - Input Array is Sorted有序数组两数之和双指针解法剖析LeetCode Go 题解167. Two Sum II Input Array is Sorted有序数组两数之和双指针解法剖析 本篇指南以 Lee示例工程剑指 Offer 57 和为 s 的两个数字对撞双指针解排序数组两数之和剑指 Offer 57 和为 s 的两个数字对撞双指针解排序数组两数之和 本文讲解《剑指 Offer》中和为 s 的两个数字一题的解法核心由于题目保证输示例工程CS-Notes 剑指 Offer 57.1有序数组“和为 S 的两个数字”双指针解法与最小乘积原理详解CS Notes 剑指 Offer 57.1有序数组“和为 S 的两个数字”双指针解法与最小乘积原理详解 本篇基于 CS Notes 仓库中的剑指 Offer知识库文档教程上一篇全平台直播弹幕抓取终极解决方案构建企业级实时数据基础设施下一篇免Steam客户端下载创意工坊模组WorkshopDL完整指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考