1. 题目拆解先弄清有序数组版究竟改了什么刷过LeetCode的朋友对两数之和都不陌生经典中的经典。大多数人入门第一题就是它但很多人刷完无序版之后看到有序数组版反而懵了——这两题到底有什么区别解题思路要不要变哈希表还能不能用了先把这个最基础的问题说透。无序版题目是给定数组找出两个数使它们的和等于目标值返回下标。有序数组版只改了一个条件数组是升序排列的。就是这一个看似不起眼的改动把题目从必须借助额外数据结构变成了可以用更优雅的数学解法。我打个比方帮助理解。无序版像是在一个没有整理过的书架上找两本书它们的页码相加刚好等于某个数你只能一本本翻翻完还得记住哪本在哪所以需要笔记本哈希表记录。而有序数组版等于书架已经按页码排好了这时候你站在书架两端根据当前两本书页数和与目标的差距往中间试探几步就能锁定目标。这个思路就是双指针。说到这儿很多人的第一反应可能是那我直接用无序版的哈希表解法不就行了吗答案是可以但没吃到这个题的核心考点。有序数组版的隐藏考点是空间复杂度能不能降到O(1)以及你知不知道为什么双指针不会漏答案。盲目套哈希表等于自动放弃了这题最有价值的部分。经典题目往往一题多解有序数组版的价值就在这个多解上暴力法最直观二分法体现有序结构的利用哈希法万能但空间换时间双指针则是时间和空间兼得的优雅解。下面我按从笨到聪明、从容易想到到需要想一想的顺序把这几种解法逐一拆开讲并给出可跑的代码。不管你是刚开始刷题的萌新还是准备面试的求职者都能找到自己能上手的一层。2. 从暴力到哈希先理解这题为什么不能无脑套用2.1 暴力枚举什么时候它能用暴力解法是两层循环把每一对组合都试一遍。代码逻辑非常简单外层指针i从左到右内层指针j从i1到末尾判断nums[i] nums[j]是否等于target找到就返回下标对。public int[] twoSum(int[] nums, int target) { for (int i 0; i nums.length; i) { for (int j i 1; j nums.length; j) { if (nums[i] nums[j] target) { return new int[] {i, j}; } } } return new int[0]; }这题用暴力法能跑通吗能。尤其数组长度小比如几百以内时运行毫无压力。但我要直说暴力法在这题里只适合用来验证其他解法的正确性靠它碰运气拿offer是不现实的。原因很简单O(n²)的时间复杂度数组长度从1000变成10000运算次数直接放大100倍面试官要的可不是这个。2.2 哈希表解法行得通但有个隐藏问题无序版的经典解法是哈希表遍历数组每到一个元素就查一下target - nums[i]是否已经在表里。有序数组版同样可以这么做public int[] twoSum(int[] nums, int target) { MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; if (map.containsKey(complement)) { return new int[] {map.get(complement), i}; } map.put(nums[i], i); } return new int[0]; }但这里有个很多人踩过的坑如果你先一次性把所有元素放进map再遍历查找遇到数组中存在重复元素的情况就会出错。比如数组是[3, 3]target是6你先把两个3都放进map键就只能存一个另一个下标被覆盖了回头就找不到正确结果。正确做法是像上面代码那样边遍历边存保证每个元素在被查询时map里只存了它之前的下标不会出现覆盖问题。如果面试时你写哈希表解法我建议顺手把这个细节讲给面试官听这能体现你对边界情况的敏感度。哈希法的问题在于空间复杂度是O(n)对有序数组来说这是用空间换时间的解法不是最优解。但它的价值在于它是唯一不需要数组有序也能跑的通用方案。也就是说面试官如果先问无序版再追问有序版你不需要推翻之前的思路而是可以顺着说有序数组可以进一步优化空间。2.3 为什么有序数组值得单独拿出来讲哈希表能通吃所有找两数之和的题目那为什么还要单独出一个有序数组版因为这题想考察的本质上是你对有序这个条件的敏感度。数据结构课程里讲过有序结构最大的价值是可以利用天然的顺序关系做二分、裁剪、迅速排除不可能的解。有序数组版的两数之和就是这个知识点在面试题中的应用。无序数组里任何两个位置都是平等的你不知道某个元素后面跟着什么只能穷举或者用哈希表记忆。但有序数组里元素的相对大小关系是确定的这让跳过不可能的情况成为可能。双指针之所以能成立靠的正是这个相对关系第二节详细展开。3. 双指针解法为什么从两端往中间走不会漏解3.1 指针怎么走一个具体的走法演示双指针的思路一句话就能说清左指针指向数组头右指针指向数组尾计算两数之和如果大于target说明和太大右指针左移如果小于target说明和太小左指针右移相等就返回。拿力扣原题的示例来走一遍nums [2, 7, 11, 15]target 9。初始left 0right 3nums[0]nums[3] 215 17大于9说明右边这个15太大了任何数加15都不会等于9所以right--。right 2。此时nums[0]nums[2] 211 13还是大于911也大了right--。right 1。此时nums[0]nums[1] 27 9正好相等返回[0, 1]。整个过程只移动了3次指针没有任何额外空间。如果用暴力法这组数据要先试(0,1)...(0,3)再试(1,2)...浪费很多不必要的工作量这就是有序结构带来的裁剪能力。3.2 关键证明跳过的那一步凭什么可以跳过很多人第一次看双指针解法最大的疑惑不是怎么走而是为什么可以这样走——你怎么知道右指针左移后左边那些元素就不需要再和原来的右指针元素组合了换句话说会不会漏掉某种情况这里得把逻辑讲透。以初始位置left0、right3为例此时sum target。因为数组升序nums[0]已经是整个数组最小的元素了它和最大的元素nums[3]相加都大于target那它和任何其他元素相加必然大于target。为什么其他元素都不大于nums[3]所以nums[0] 任意元素 ≤ nums[0] nums[3]这个不等式成立而后者已经大于target了。结论是nums[3]永远不会是答案的一部分这个元素可以直接丢掉右指针左移。同理如果sum target说明nums[right]已经是最大的了它和当前最左的nums[left]相加都小于target那它和更右边的任何元素相加也必然小于target当前nums[left]永远不会是答案的一部分左指针右移。这就是双指针正确性的核心每一步移动都能证明被移过去的那个指针指向的元素绝对不可能是答案。不是感觉差不多该移了而是通过不等式严格推出来它不可能。理解到这一层你就拿到这题最值钱的东西了。3.3 为什么不能一个指针从头走到尾还有一个常见的疑问是既然是升序数组能不能只用一个指针另一个指针配合二分查找比如固定left在剩余区间里二分查找target - nums[left]这确实是个优化版思路下一篇讲解法时会单独讨论但我要先指出它的代价二分查找单次O(logn)外层n次循环总复杂度O(nlogn)比双指针的O(n)差一个档次。面试官如果问了还能不能更快双指针就是那个更快的答案。我也见过有人把双指针理解成撞指针——两边往中间靠直到相遇。这个理解对了一半。实际上并不是任何情况下都一路走到黑而是在不断判断当前和与target关系的前提下移动可能左移几次右移几次不一定是严格交替。理解到这个层面就够了。4. 代码落地与细节实现写对边界条件是这题的第一道坎4.1 先写框架再填细节为什么这样组织最稳写代码这事儿最忌讳闷头直接敲。我习惯先想清楚边界条件再动手。这题的核心边界有三个left必须小于right不能指向同一个元素因为题目要求两个不同的数、数组不能为空空数组根本进不了循环、找到后立刻返回题目说只有唯一答案所以遇到即返回不需要继续找。以Java为例完整可跑的代码长这样public int[] twoSum(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { return new int[] {left, right}; } else if (sum target) { left; } else { right--; } } return new int[0]; // 没有解返回空数组 }注意几点。第一循环条件是left right而不是left right否则当左右指针指向同一个元素时它会被当成两个数来算这是逻辑错误。第二空数组的判断可以放在方法开头也可以利用while循环天然跳过问题不大但写上更清晰。第三返回值如果没找到我习惯返回new int[0]而不是返回null——在LeetCode这类平台上返回null容易引发调用方的空指针问题返回空数组更安全。4.2 C版本对比指针操作的惯用法同样的思路C写出来会更贴近底层操作。C的vector和迭代器让人条件反射地想直接用下标操作代码和Java版本几乎没有差别class Solution { public: vectorint twoSum(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { return {left, right}; } else if (sum target) { left; } else { right--; } } return {}; } };C版本有一个隐藏注意点nums.size()返回的是size_t类型是无符号整数当你用nums.size() - 1赋给int类型的right时如果数组为空这里会发生下溢变成一个巨大的正数。但题目通常保证数组非空我写的时候还是习惯加一嘴判断或者用int right (int)nums.size() - 1;先转换再减避免类型隐患。4.3 为什么这里不需要二分法从复杂度角度聊聊取舍如果要问这个题最好玩的地方我觉得是它能自然引出二分法能不能用的讨论。有人会想既然数组有序固定一个数后另一个数用二分找不行吗当然行而且值得写一版试试。这里给出一个参考实现public int[] twoSumBinary(int[] nums, int target) { for (int i 0; i nums.length; i) { int left i 1; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target - nums[i]) { return new int[] {i, mid}; } else if (nums[mid] target - nums[i]) { left mid 1; } else { right mid - 1; } } } return new int[0]; }这个版本思路是枚举每个数在剩余区间二分找补数。复杂度O(nlogn)空间O(1)。面试时你可以把它作为中间答案抛出来然后顺着还能不能更快问句引出双指针O(n)解。整个过程自然流畅也体现了你对复杂度分析的敏感度。不过要说清楚当数组有序时双指针一定比二分枚举更优。原因在于二分枚举每次只利用一次有序性而双指针每次都同时利用左右两端的极值关系把不可能的解一次性排除一整行。这在算法题里是一个很值得品味的优化思路。5. 变式题型与实战经验刷一题顶三题的拆解方法5.1 多个解的变式怎么把所有组合都找出来原题说只有唯一答案这是最简单的情况。真正面试的时候面试官随时可能追加一句如果答案不唯一呢比如数组[1, 2, 3, 4, 5, 6]target7答案有(1,6)、(2,5)、(3,4)三对。此时双指针解法怎么改关键改动是找到一对答案后不能立刻返回而是继续移动指针。但需要先想清楚找到(1,6)后left和right如何移动如果只移动一个指针可能会出现重复组合。正确做法是同时把left右移、right左移因为1和6已经配过对了它们都不会再和其他元素组成新答案——以1为例它和任何比6小的数相加都小于7不可能等于target以6为例它和任何比1大的数相加都大于7也不可能等于target。public Listint[] twoSumAll(int[] nums, int target) { Listint[] result new ArrayList(); int left 0; int right nums.length - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { result.add(new int[] {nums[left], nums[right]}); left; right--; } else if (sum target) { left; } else { right--; } } return result; }如果数组里有重复值比如[1, 1, 2, 2]target3这个版本会输出两组(1,2)组内数字相同但下标不同。如果要求去重就得在移动指针时加上跳过重复值的逻辑。这几个变式层层递进能一次性把双指针的用法练透。5.2 三个数之和两数之和的自然延伸另一个高频变式是三数之和LeetCode 15。它的解法是固定一个数然后在剩余区间上用双指针找两数之和等于target - nums[i]。这就是两数之和有序数组版的直接应用题。public ListListInteger threeSum(int[] nums) { Arrays.sort(nums); ListListInteger result new ArrayList(); for (int i 0; i nums.length - 2; i) { if (i 0 nums[i] nums[i - 1]) continue; // 跳过重复数 int left i 1; int right nums.length - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { result.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--; } else if (sum 0) { left; } else { right--; } } } return result; }三数之和的核心复杂度是排序O(nlogn)加双指针O(n²)比暴力三重循环的O(n³)快了一个数量级。面试时从两数之和讲到三数之和再讲到四数之和固定两个数双指针找另外两个整个知识链条是连贯的这套变式能力比死记十道题有用得多。5.3 实战踩坑我自己刷题时遇到过的几类低级错误第一类错误是数据类型溢出。数组元素是int两个大int相加可能溢出成负数导致比较结果错误。LeetCode 167虽然给的测试用例不会溢出但实际生产环境必须考虑。稳妥做法是相加时先转成long再比较或者先判断target - nums[left]与nums[right]是否相等用减法代替加法从根上避开溢出。if (target - nums[left] nums[right]) { // 用减法代替加法第二类错误是盲目照搬无序版的代码。我第一次做这题时惯性思维直接写了HashMap解法跑通了但总感觉不对——有序数组这么重要的信息没用上这题白做了。后来把双指针解法写出来才有一种原来如此的通透感。所以刷题不能只看能不能过要看这个题想考什么。第三类错误是不理解返回要求。LeetCode 167要求返回下标且从1开始计数返回值是[left1, right1]LeetCode 1要求返回原数组下标。很多人在这里栽跟头代码逻辑全对就是返回时忘了1。我建议把两道题放在一起刷区分清楚它们的细节差异。6. 一道题三种语言不同语言的惯用法和版本差异6.1 Python版本切片与下标的取舍Python写这题最简洁但有一个新手容易踩的坑切片操作会生成新数组比如nums[left:right]会复制一段如果在大数组里频繁切片空间开销不小。所以即便Python写着方便我还是建议直接用下标操作避免切片。def two_sum(nums, target): left, right 0, len(nums) - 1 while left right: cur_sum nums[left] nums[right] if cur_sum target: return [left, right] elif cur_sum target: left 1 else: right - 1 return []Python的while left right、left 1读起来非常自然这也是Python适合刷题的原因之一——思路和代码的对应关系直白不容易在语言层面绕弯子。不过Python的list没有直接的下标越界防御你需要格外注意right的初始值不能为-1空数组时否则nums[-1]会取到倒数第一个元素这种隐晦的错误很浪费调试时间。6.2 复杂度和优化方向这道题能不能扩展到大数据场景这道题的规模其实是把n控制在合理范围内但真实业务里数组可能有几百万个元素。双指针O(n)当然是好选择但如果内存紧张、数组无法全部载入内存那就要考虑外部排序、分段读取等方案了。这时候双指针的原地操作优势反而可能变成劣势——因为在数组不是在内存里连续存放的场景随机访问性能会下降。这篇不展开只是提醒一点算法题背后的工程考量才是面试官真正想听的东西。6.3 做题顺序建议两数之和家族怎么刷最有效我的建议是按照无序版 → 有序版 → 三数之和 → 四数之和的顺序刷。每一题都是前一题的延伸无序版教你如何用哈希牺牲空间换时间有序版教你如何利用有序性把空间降到O(1)三数之和教你如何把多指针嵌套使用四数之和则是三数之和的再扩展。这个链条刷下来双指针、哈希表、排序、去重这些核心技巧全都涉及了比零散刷几十道题效果更好。刷的时候给自己一个要求每道题至少写两种解法。无序版写哈希和暴力有序版写双指针和二分。写完之后在注释里标明时间复杂度和空间复杂度这个习惯会让你在面试时不假思索就能答出复杂度的推导过程。7. 三种解法全景对比与选择建议7.1 复杂度对照表为了让你一目了然我把三种解法整理成对照表解法时间复杂度空间复杂度是否需要有序适用场景暴力枚举O(n²)O(1)否仅限数组极小或用来验证其他解法哈希表O(n)O(n)否无序数组首选通用性最强二分枚举O(nlogn)O(1)是有序数组可用但不如双指针快双指针O(n)O(1)是有序数组最优解空间友好从表格能直观看出有序数组场景下双指针是综合最优解时间复杂度和哈希持平空间复杂度却降到O(1)。遇到只能使用常量级额外空间这类限制条件时哈希解法直接出局双指针就是唯一答案。7.2 怎么跟面试官讲这题表达顺序比答案本身更重要我把这题的面试表达顺序总结为五步亲测有效先说暴力法两层循环O(n²)给面试官一个基准线。再提优化思路既然无序可以用哈希表把查找降到O(1)整体O(n)。重点强调但题目给的是有序数组有序结构有更强的信息可以利用。代码写双指针从两端逼近每次确定排除一个元素O(n)时间O(1)空间。最后补充边界循环条件是left right返回值是否要1重复元素怎么处理等。这套打法覆盖了从暴力到最优从通用到利用题目特性从思路到边界三条线面试官很难挑出明显漏洞。如果你还是学生在数据结构期末复习时也可以用这个思路组织答案把自己当成面试官问自己为什么不能只用哈希表双指针漏解吗边界条件有哪些三问答完这题就算真正掌握了。8. 我的几点体会这些才是刷题几年后真正沉淀下来的东西刷题几年回头看这题我觉得最值得说的反而不是双指针本身而是它揭示出的几条通用规律。第一题目里每个限定条件都不是废话。有序数组四个字决定了最优解的方向。很多人在笔试里栽跟头不是因为不会算法而是因为没读懂题——把有序数组当成无序数组做白白浪费了题目给的提示。做题前花五分钟划出题目的限定条件比匆忙写代码节省更多时间。第二空间复杂度和时间复杂度的权衡是这个行业的日常。哈希表解法O(n)时间O(n)空间双指针O(n)时间O(1)空间看起来好像双指针全面碾压但哈希表在一个重要场景下依然不可替代数组是无序的。真实业务里你拿到的数据往往不是排好序的强制排序可能又要多花O(nlogn)的时间。所以最优解不是绝对的而是在给定条件下最优的。第三也是我想特别强调的别小看简单题。两数之和看起来简单但它是双指针、哈希表、二分查找、复杂度分析、边界条件处理这几个核心知识点的交汇点。把这题彻底吃透比你刷十道难度中等但思路重复的题有价值得多。我见过太多人追求刷题数量却忽略了把一道经典题拆开揉碎、举一反三这其实是本末倒置了。如果你能把这题从暴力到双指针、从两数到三数、从下标到去重全部写清楚那数据结构与算法之路上两数之和这一关就算真正迈过去了。往后的三数之和、四数之和、盛最多水的容器、接雨水……你会发现它们都跳不出今天聊的双指针框架。这就是刷题的复利效应。
有序数组两数之和：双指针解法原理与复杂度优化
1. 题目拆解先弄清有序数组版究竟改了什么刷过LeetCode的朋友对两数之和都不陌生经典中的经典。大多数人入门第一题就是它但很多人刷完无序版之后看到有序数组版反而懵了——这两题到底有什么区别解题思路要不要变哈希表还能不能用了先把这个最基础的问题说透。无序版题目是给定数组找出两个数使它们的和等于目标值返回下标。有序数组版只改了一个条件数组是升序排列的。就是这一个看似不起眼的改动把题目从必须借助额外数据结构变成了可以用更优雅的数学解法。我打个比方帮助理解。无序版像是在一个没有整理过的书架上找两本书它们的页码相加刚好等于某个数你只能一本本翻翻完还得记住哪本在哪所以需要笔记本哈希表记录。而有序数组版等于书架已经按页码排好了这时候你站在书架两端根据当前两本书页数和与目标的差距往中间试探几步就能锁定目标。这个思路就是双指针。说到这儿很多人的第一反应可能是那我直接用无序版的哈希表解法不就行了吗答案是可以但没吃到这个题的核心考点。有序数组版的隐藏考点是空间复杂度能不能降到O(1)以及你知不知道为什么双指针不会漏答案。盲目套哈希表等于自动放弃了这题最有价值的部分。经典题目往往一题多解有序数组版的价值就在这个多解上暴力法最直观二分法体现有序结构的利用哈希法万能但空间换时间双指针则是时间和空间兼得的优雅解。下面我按从笨到聪明、从容易想到到需要想一想的顺序把这几种解法逐一拆开讲并给出可跑的代码。不管你是刚开始刷题的萌新还是准备面试的求职者都能找到自己能上手的一层。2. 从暴力到哈希先理解这题为什么不能无脑套用2.1 暴力枚举什么时候它能用暴力解法是两层循环把每一对组合都试一遍。代码逻辑非常简单外层指针i从左到右内层指针j从i1到末尾判断nums[i] nums[j]是否等于target找到就返回下标对。public int[] twoSum(int[] nums, int target) { for (int i 0; i nums.length; i) { for (int j i 1; j nums.length; j) { if (nums[i] nums[j] target) { return new int[] {i, j}; } } } return new int[0]; }这题用暴力法能跑通吗能。尤其数组长度小比如几百以内时运行毫无压力。但我要直说暴力法在这题里只适合用来验证其他解法的正确性靠它碰运气拿offer是不现实的。原因很简单O(n²)的时间复杂度数组长度从1000变成10000运算次数直接放大100倍面试官要的可不是这个。2.2 哈希表解法行得通但有个隐藏问题无序版的经典解法是哈希表遍历数组每到一个元素就查一下target - nums[i]是否已经在表里。有序数组版同样可以这么做public int[] twoSum(int[] nums, int target) { MapInteger, Integer map new HashMap(); for (int i 0; i nums.length; i) { int complement target - nums[i]; if (map.containsKey(complement)) { return new int[] {map.get(complement), i}; } map.put(nums[i], i); } return new int[0]; }但这里有个很多人踩过的坑如果你先一次性把所有元素放进map再遍历查找遇到数组中存在重复元素的情况就会出错。比如数组是[3, 3]target是6你先把两个3都放进map键就只能存一个另一个下标被覆盖了回头就找不到正确结果。正确做法是像上面代码那样边遍历边存保证每个元素在被查询时map里只存了它之前的下标不会出现覆盖问题。如果面试时你写哈希表解法我建议顺手把这个细节讲给面试官听这能体现你对边界情况的敏感度。哈希法的问题在于空间复杂度是O(n)对有序数组来说这是用空间换时间的解法不是最优解。但它的价值在于它是唯一不需要数组有序也能跑的通用方案。也就是说面试官如果先问无序版再追问有序版你不需要推翻之前的思路而是可以顺着说有序数组可以进一步优化空间。2.3 为什么有序数组值得单独拿出来讲哈希表能通吃所有找两数之和的题目那为什么还要单独出一个有序数组版因为这题想考察的本质上是你对有序这个条件的敏感度。数据结构课程里讲过有序结构最大的价值是可以利用天然的顺序关系做二分、裁剪、迅速排除不可能的解。有序数组版的两数之和就是这个知识点在面试题中的应用。无序数组里任何两个位置都是平等的你不知道某个元素后面跟着什么只能穷举或者用哈希表记忆。但有序数组里元素的相对大小关系是确定的这让跳过不可能的情况成为可能。双指针之所以能成立靠的正是这个相对关系第二节详细展开。3. 双指针解法为什么从两端往中间走不会漏解3.1 指针怎么走一个具体的走法演示双指针的思路一句话就能说清左指针指向数组头右指针指向数组尾计算两数之和如果大于target说明和太大右指针左移如果小于target说明和太小左指针右移相等就返回。拿力扣原题的示例来走一遍nums [2, 7, 11, 15]target 9。初始left 0right 3nums[0]nums[3] 215 17大于9说明右边这个15太大了任何数加15都不会等于9所以right--。right 2。此时nums[0]nums[2] 211 13还是大于911也大了right--。right 1。此时nums[0]nums[1] 27 9正好相等返回[0, 1]。整个过程只移动了3次指针没有任何额外空间。如果用暴力法这组数据要先试(0,1)...(0,3)再试(1,2)...浪费很多不必要的工作量这就是有序结构带来的裁剪能力。3.2 关键证明跳过的那一步凭什么可以跳过很多人第一次看双指针解法最大的疑惑不是怎么走而是为什么可以这样走——你怎么知道右指针左移后左边那些元素就不需要再和原来的右指针元素组合了换句话说会不会漏掉某种情况这里得把逻辑讲透。以初始位置left0、right3为例此时sum target。因为数组升序nums[0]已经是整个数组最小的元素了它和最大的元素nums[3]相加都大于target那它和任何其他元素相加必然大于target。为什么其他元素都不大于nums[3]所以nums[0] 任意元素 ≤ nums[0] nums[3]这个不等式成立而后者已经大于target了。结论是nums[3]永远不会是答案的一部分这个元素可以直接丢掉右指针左移。同理如果sum target说明nums[right]已经是最大的了它和当前最左的nums[left]相加都小于target那它和更右边的任何元素相加也必然小于target当前nums[left]永远不会是答案的一部分左指针右移。这就是双指针正确性的核心每一步移动都能证明被移过去的那个指针指向的元素绝对不可能是答案。不是感觉差不多该移了而是通过不等式严格推出来它不可能。理解到这一层你就拿到这题最值钱的东西了。3.3 为什么不能一个指针从头走到尾还有一个常见的疑问是既然是升序数组能不能只用一个指针另一个指针配合二分查找比如固定left在剩余区间里二分查找target - nums[left]这确实是个优化版思路下一篇讲解法时会单独讨论但我要先指出它的代价二分查找单次O(logn)外层n次循环总复杂度O(nlogn)比双指针的O(n)差一个档次。面试官如果问了还能不能更快双指针就是那个更快的答案。我也见过有人把双指针理解成撞指针——两边往中间靠直到相遇。这个理解对了一半。实际上并不是任何情况下都一路走到黑而是在不断判断当前和与target关系的前提下移动可能左移几次右移几次不一定是严格交替。理解到这个层面就够了。4. 代码落地与细节实现写对边界条件是这题的第一道坎4.1 先写框架再填细节为什么这样组织最稳写代码这事儿最忌讳闷头直接敲。我习惯先想清楚边界条件再动手。这题的核心边界有三个left必须小于right不能指向同一个元素因为题目要求两个不同的数、数组不能为空空数组根本进不了循环、找到后立刻返回题目说只有唯一答案所以遇到即返回不需要继续找。以Java为例完整可跑的代码长这样public int[] twoSum(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { return new int[] {left, right}; } else if (sum target) { left; } else { right--; } } return new int[0]; // 没有解返回空数组 }注意几点。第一循环条件是left right而不是left right否则当左右指针指向同一个元素时它会被当成两个数来算这是逻辑错误。第二空数组的判断可以放在方法开头也可以利用while循环天然跳过问题不大但写上更清晰。第三返回值如果没找到我习惯返回new int[0]而不是返回null——在LeetCode这类平台上返回null容易引发调用方的空指针问题返回空数组更安全。4.2 C版本对比指针操作的惯用法同样的思路C写出来会更贴近底层操作。C的vector和迭代器让人条件反射地想直接用下标操作代码和Java版本几乎没有差别class Solution { public: vectorint twoSum(vectorint nums, int target) { int left 0, right nums.size() - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { return {left, right}; } else if (sum target) { left; } else { right--; } } return {}; } };C版本有一个隐藏注意点nums.size()返回的是size_t类型是无符号整数当你用nums.size() - 1赋给int类型的right时如果数组为空这里会发生下溢变成一个巨大的正数。但题目通常保证数组非空我写的时候还是习惯加一嘴判断或者用int right (int)nums.size() - 1;先转换再减避免类型隐患。4.3 为什么这里不需要二分法从复杂度角度聊聊取舍如果要问这个题最好玩的地方我觉得是它能自然引出二分法能不能用的讨论。有人会想既然数组有序固定一个数后另一个数用二分找不行吗当然行而且值得写一版试试。这里给出一个参考实现public int[] twoSumBinary(int[] nums, int target) { for (int i 0; i nums.length; i) { int left i 1; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target - nums[i]) { return new int[] {i, mid}; } else if (nums[mid] target - nums[i]) { left mid 1; } else { right mid - 1; } } } return new int[0]; }这个版本思路是枚举每个数在剩余区间二分找补数。复杂度O(nlogn)空间O(1)。面试时你可以把它作为中间答案抛出来然后顺着还能不能更快问句引出双指针O(n)解。整个过程自然流畅也体现了你对复杂度分析的敏感度。不过要说清楚当数组有序时双指针一定比二分枚举更优。原因在于二分枚举每次只利用一次有序性而双指针每次都同时利用左右两端的极值关系把不可能的解一次性排除一整行。这在算法题里是一个很值得品味的优化思路。5. 变式题型与实战经验刷一题顶三题的拆解方法5.1 多个解的变式怎么把所有组合都找出来原题说只有唯一答案这是最简单的情况。真正面试的时候面试官随时可能追加一句如果答案不唯一呢比如数组[1, 2, 3, 4, 5, 6]target7答案有(1,6)、(2,5)、(3,4)三对。此时双指针解法怎么改关键改动是找到一对答案后不能立刻返回而是继续移动指针。但需要先想清楚找到(1,6)后left和right如何移动如果只移动一个指针可能会出现重复组合。正确做法是同时把left右移、right左移因为1和6已经配过对了它们都不会再和其他元素组成新答案——以1为例它和任何比6小的数相加都小于7不可能等于target以6为例它和任何比1大的数相加都大于7也不可能等于target。public Listint[] twoSumAll(int[] nums, int target) { Listint[] result new ArrayList(); int left 0; int right nums.length - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { result.add(new int[] {nums[left], nums[right]}); left; right--; } else if (sum target) { left; } else { right--; } } return result; }如果数组里有重复值比如[1, 1, 2, 2]target3这个版本会输出两组(1,2)组内数字相同但下标不同。如果要求去重就得在移动指针时加上跳过重复值的逻辑。这几个变式层层递进能一次性把双指针的用法练透。5.2 三个数之和两数之和的自然延伸另一个高频变式是三数之和LeetCode 15。它的解法是固定一个数然后在剩余区间上用双指针找两数之和等于target - nums[i]。这就是两数之和有序数组版的直接应用题。public ListListInteger threeSum(int[] nums) { Arrays.sort(nums); ListListInteger result new ArrayList(); for (int i 0; i nums.length - 2; i) { if (i 0 nums[i] nums[i - 1]) continue; // 跳过重复数 int left i 1; int right nums.length - 1; while (left right) { int sum nums[i] nums[left] nums[right]; if (sum 0) { result.add(Arrays.asList(nums[i], nums[left], nums[right])); while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) right--; left; right--; } else if (sum 0) { left; } else { right--; } } } return result; }三数之和的核心复杂度是排序O(nlogn)加双指针O(n²)比暴力三重循环的O(n³)快了一个数量级。面试时从两数之和讲到三数之和再讲到四数之和固定两个数双指针找另外两个整个知识链条是连贯的这套变式能力比死记十道题有用得多。5.3 实战踩坑我自己刷题时遇到过的几类低级错误第一类错误是数据类型溢出。数组元素是int两个大int相加可能溢出成负数导致比较结果错误。LeetCode 167虽然给的测试用例不会溢出但实际生产环境必须考虑。稳妥做法是相加时先转成long再比较或者先判断target - nums[left]与nums[right]是否相等用减法代替加法从根上避开溢出。if (target - nums[left] nums[right]) { // 用减法代替加法第二类错误是盲目照搬无序版的代码。我第一次做这题时惯性思维直接写了HashMap解法跑通了但总感觉不对——有序数组这么重要的信息没用上这题白做了。后来把双指针解法写出来才有一种原来如此的通透感。所以刷题不能只看能不能过要看这个题想考什么。第三类错误是不理解返回要求。LeetCode 167要求返回下标且从1开始计数返回值是[left1, right1]LeetCode 1要求返回原数组下标。很多人在这里栽跟头代码逻辑全对就是返回时忘了1。我建议把两道题放在一起刷区分清楚它们的细节差异。6. 一道题三种语言不同语言的惯用法和版本差异6.1 Python版本切片与下标的取舍Python写这题最简洁但有一个新手容易踩的坑切片操作会生成新数组比如nums[left:right]会复制一段如果在大数组里频繁切片空间开销不小。所以即便Python写着方便我还是建议直接用下标操作避免切片。def two_sum(nums, target): left, right 0, len(nums) - 1 while left right: cur_sum nums[left] nums[right] if cur_sum target: return [left, right] elif cur_sum target: left 1 else: right - 1 return []Python的while left right、left 1读起来非常自然这也是Python适合刷题的原因之一——思路和代码的对应关系直白不容易在语言层面绕弯子。不过Python的list没有直接的下标越界防御你需要格外注意right的初始值不能为-1空数组时否则nums[-1]会取到倒数第一个元素这种隐晦的错误很浪费调试时间。6.2 复杂度和优化方向这道题能不能扩展到大数据场景这道题的规模其实是把n控制在合理范围内但真实业务里数组可能有几百万个元素。双指针O(n)当然是好选择但如果内存紧张、数组无法全部载入内存那就要考虑外部排序、分段读取等方案了。这时候双指针的原地操作优势反而可能变成劣势——因为在数组不是在内存里连续存放的场景随机访问性能会下降。这篇不展开只是提醒一点算法题背后的工程考量才是面试官真正想听的东西。6.3 做题顺序建议两数之和家族怎么刷最有效我的建议是按照无序版 → 有序版 → 三数之和 → 四数之和的顺序刷。每一题都是前一题的延伸无序版教你如何用哈希牺牲空间换时间有序版教你如何利用有序性把空间降到O(1)三数之和教你如何把多指针嵌套使用四数之和则是三数之和的再扩展。这个链条刷下来双指针、哈希表、排序、去重这些核心技巧全都涉及了比零散刷几十道题效果更好。刷的时候给自己一个要求每道题至少写两种解法。无序版写哈希和暴力有序版写双指针和二分。写完之后在注释里标明时间复杂度和空间复杂度这个习惯会让你在面试时不假思索就能答出复杂度的推导过程。7. 三种解法全景对比与选择建议7.1 复杂度对照表为了让你一目了然我把三种解法整理成对照表解法时间复杂度空间复杂度是否需要有序适用场景暴力枚举O(n²)O(1)否仅限数组极小或用来验证其他解法哈希表O(n)O(n)否无序数组首选通用性最强二分枚举O(nlogn)O(1)是有序数组可用但不如双指针快双指针O(n)O(1)是有序数组最优解空间友好从表格能直观看出有序数组场景下双指针是综合最优解时间复杂度和哈希持平空间复杂度却降到O(1)。遇到只能使用常量级额外空间这类限制条件时哈希解法直接出局双指针就是唯一答案。7.2 怎么跟面试官讲这题表达顺序比答案本身更重要我把这题的面试表达顺序总结为五步亲测有效先说暴力法两层循环O(n²)给面试官一个基准线。再提优化思路既然无序可以用哈希表把查找降到O(1)整体O(n)。重点强调但题目给的是有序数组有序结构有更强的信息可以利用。代码写双指针从两端逼近每次确定排除一个元素O(n)时间O(1)空间。最后补充边界循环条件是left right返回值是否要1重复元素怎么处理等。这套打法覆盖了从暴力到最优从通用到利用题目特性从思路到边界三条线面试官很难挑出明显漏洞。如果你还是学生在数据结构期末复习时也可以用这个思路组织答案把自己当成面试官问自己为什么不能只用哈希表双指针漏解吗边界条件有哪些三问答完这题就算真正掌握了。8. 我的几点体会这些才是刷题几年后真正沉淀下来的东西刷题几年回头看这题我觉得最值得说的反而不是双指针本身而是它揭示出的几条通用规律。第一题目里每个限定条件都不是废话。有序数组四个字决定了最优解的方向。很多人在笔试里栽跟头不是因为不会算法而是因为没读懂题——把有序数组当成无序数组做白白浪费了题目给的提示。做题前花五分钟划出题目的限定条件比匆忙写代码节省更多时间。第二空间复杂度和时间复杂度的权衡是这个行业的日常。哈希表解法O(n)时间O(n)空间双指针O(n)时间O(1)空间看起来好像双指针全面碾压但哈希表在一个重要场景下依然不可替代数组是无序的。真实业务里你拿到的数据往往不是排好序的强制排序可能又要多花O(nlogn)的时间。所以最优解不是绝对的而是在给定条件下最优的。第三也是我想特别强调的别小看简单题。两数之和看起来简单但它是双指针、哈希表、二分查找、复杂度分析、边界条件处理这几个核心知识点的交汇点。把这题彻底吃透比你刷十道难度中等但思路重复的题有价值得多。我见过太多人追求刷题数量却忽略了把一道经典题拆开揉碎、举一反三这其实是本末倒置了。如果你能把这题从暴力到双指针、从两数到三数、从下标到去重全部写清楚那数据结构与算法之路上两数之和这一关就算真正迈过去了。往后的三数之和、四数之和、盛最多水的容器、接雨水……你会发现它们都跳不出今天聊的双指针框架。这就是刷题的复利效应。