1. 双指针技巧从直觉到代码的思维跃迁如果你写过一段时间的C尤其是在处理数组、字符串或者链表这类线性数据结构时大概率遇到过这样的场景你需要同时追踪两个位置一个在前面“探路”一个在后面“扫尾”或者一个从左边出发一个从右边逼近。这种“两个指针协同工作”的思路就是双指针技巧的核心。它不是什么高深的算法更像是一种编程范式一种解决问题的思维方式。我第一次真正体会到它的威力是在解决LeetCode上那道经典的“两数之和 II - 输入有序数组”时。当看到别人用O(n)时间、O(1)空间就优雅地解决了问题而我还在纠结嵌套循环时那种“原来可以这样”的顿悟感至今记忆犹新。双指针技巧之所以重要是因为它能将许多看似需要O(n²)暴力搜索的问题优化到O(n)的线性时间复杂度。它不依赖于任何特殊的数据结构只利用问题本身的特性比如有序性通过指针的移动来缩小搜索空间是面试中检验候选人是否具备优化思维和代码掌控力的高频考点。无论是准备求职面试还是想在日常开发中写出更高效的代码掌握双指针都是绕不开的一课。这篇文章我将带你从最基础的快慢指针、左右指针讲起一直深入到它在滑动窗口、链表环检测等复杂场景中的应用并结合大量代码示例和我的踩坑经验让你彻底吃透这个技巧。2. 双指针的核心思想与两种基本模式双指针顾名思义就是在遍历或处理数据时使用两个指针通常是下标或迭代器来协同完成任务。这两个指针的移动策略决定了它能解决哪类问题。理解其核心关键在于明白指针移动的“单调性”——即指针的移动方向是确定的不会来回反复从而保证每个元素最多被访问常数次这是实现O(n)复杂度的基础。2.1 同向移动指针快慢指针这是最常用的一种模式。两个指针slow和fast从同一侧通常是起始位置开始fast指针移动得更快负责探索或满足某个条件slow指针移动得慢负责维护一个符合要求的子区间或记录有效位置。核心逻辑fast指针不断向前探索当它发现一个满足条件的元素时就通知slow指针由slow指针来“接收”这个元素比如赋值、交换然后slow才向前移动一步。这样[0, slow)或[0, slow]区间内始终保持着有效数据。一个最经典的例子是原地移除有序数组中的重复项。假设给你一个升序数组nums要求原地删除重复出现的元素使得每个元素只出现一次并返回新数组的长度。int removeDuplicates(vectorint nums) { if (nums.empty()) return 0; int slow 0; // 慢指针指向下一个待放置不重复元素的位置 for (int fast 1; fast nums.size(); fast) { // 快指针遍历整个数组 if (nums[fast] ! nums[slow]) { // 发现一个新的不重复元素 slow; // 慢指针先移动到下一个位置 nums[slow] nums[fast]; // 将新元素放置过来 } // 如果相等快指针继续走慢指针不动相当于跳过了重复项 } return slow 1; // 新数组长度为慢指针索引1 }为什么这样可行因为数组是有序的所以所有相同的数字必然连续出现。fast指针一路扫描只有当它遇到一个与slow指向的数字不同的新数字时才说明我们找到了下一个不重复的元素此时应该把它放到slow的下一个位置。这个过程保证了[0, slow]区间内的所有数字都是唯一且有序的。注意这里slow的初始值和返回值的处理是新手容易出错的地方。slow指向的是最后一个有效元素的索引所以有效长度是slow 1。循环从fast 1开始是因为第一个元素nums[0]天然就是有效的不需要比较。2.2 相向移动指针左右指针这种模式通常用于已排序的数组或首尾操作明确的场景。两个指针left和right分别指向序列的开头和结尾然后根据某种条件逐步向中间靠拢。核心逻辑利用数据的有序性通过比较nums[left]和nums[right]与目标值的关系可以确定应该移动哪个指针来逼近答案。每次移动都能“淘汰”掉一部分不可能的解从而快速缩小搜索范围。最典型的例子就是开篇提到的两数之和 II。给定一个已按非递减顺序排列的整数数组numbers和一个目标值target找出两个数使它们的和等于target。vectorint twoSum(vectorint numbers, int target) { int left 0; int right numbers.size() - 1; while (left right) { int sum numbers[left] numbers[right]; if (sum target) { // 题目要求索引从1开始 return {left 1, right 1}; } else if (sum target) { // 和太小了需要增大所以移动左指针因为数组升序 left; } else { // sum target // 和太大了需要减小所以移动右指针 --right; } } // 根据题目描述保证有解所以这里不会执行到 return {}; }为什么移动指针是安全的假设当前sum target。因为数组是升序的numbers[left]是当前左指针所指的最小值numbers[right]是当前右指针所指的最大值。如果连numbers[left] numbers[right]都小于目标那么numbers[left]加上任何比numbers[right]更小的数即left固定right向左移动的所有情况只会更小更不可能等于目标。因此numbers[left]这个值已经可以彻底排除必须将left右移来尝试更大的数。反之当sum target时numbers[right]这个值也可以被排除。3. 滑动窗口同向指针的威力延伸滑动窗口是双指针技巧中一个极其重要的应用它完美诠释了如何用两个同向指针来维护一个动态的区间。这个“窗口”由left和right指针界定right负责扩大窗口纳入新元素left负责收缩窗口排除旧元素从而在遍历过程中高效地找出所有满足条件的子区间。滑动窗口常用于求解连续子数组/子字符串的极值或计数问题例如“和大于等于K的最短子数组”、“无重复字符的最长子串”。3.1 滑动窗口的通用框架一个典型的滑动窗口解法遵循以下模板int slidingWindowTemplate(vectorint nums, int k) { int left 0, right 0; // 窗口边界 [left, right) int windowSum 0; // 窗口内状态如和、字符计数等 int result 0; // 存储最终答案 while (right nums.size()) { // 1. 右扩将nums[right]加入窗口并更新窗口状态 windowSum nums[right]; right; // 2. 内循环判断窗口状态是否满足收缩条件 while (/* 窗口状态需要收缩的条件例如 windowSum k */) { // 3. 在收缩前更新最终答案例如记录最小长度 result min(result, right - left); // 注意right已右移区间是[left, right) // 4. 左缩将nums[left]移出窗口并更新窗口状态 windowSum - nums[left]; left; } // 注意对于求最长子串等问题更新答案可能放在收缩循环之外 } return result; }3.2 实战解析乘积小于K的子数组个数我们来看LeetCode 713. 乘积小于K的子数组。给定一个正整数数组nums和整数k求有多少个连续子数组的乘积严格小于k。暴力解法是枚举所有子数组计算乘积复杂度O(n²)在n最大为3*10^4时必然超时。滑动窗口如何解决核心思路维护一个乘积小于k的窗口[left, right]。对于每个固定的右边界right找到最小的左边界left使得窗口内乘积 k。那么以right为右端点的、满足条件的子数组个数就是right - left 1。int numSubarrayProductLessThanK(vectorint nums, int k) { if (k 1) return 0; // 关键如果k1因为nums[i]1乘积不可能小于1结果为0。 int left 0; long long product 1; // 用long long防止int溢出 int count 0; for (int right 0; right nums.size(); right) { product * nums[right]; // 右扩加入nums[right] // 当乘积过大时收缩左边界 while (product k) { product / nums[left]; left; } // 此时窗口[left, right]内所有子数组乘积都小于k // 以right结尾的子数组个数为 (right - left 1) count (right - left 1); } return count; }为什么是right - left 1对于当前窗口[left, right]所有以right结尾的子数组为[right],[right-1, right], ...,[left, right]。一共就是(right - left 1)个。这些子数组的乘积都小于k吗是的因为我们已经通过内层while循环保证了整个窗口的乘积 k而窗口内的所有元素都是正整数所以其任何子数组从left到right之间任意一个位置开始的乘积只会更小因为乘的数更少或相同必然也小于k。踩坑点k 1的边界情况必须单独处理。因为如果k1题目要求乘积“小于”1而数组元素是正整数最小乘积为1所以不可能有子数组满足条件直接返回0。如果不处理product初始为1永远无法进入收缩循环会导致逻辑错误或死循环。4. 双指针在链表中的应用不仅仅是环检测链表由于其单向遍历的特性双指针技巧在这里大放异彩最著名的莫过于Floyd判圈算法龟兔赛跑算法。4.1 检测链表是否有环问题给定一个链表的头节点head判断链表中是否有环。struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; bool hasCycle(ListNode *head) { if (!head || !head-next) return false; ListNode *slow head; ListNode *fast head; // 快指针每次走两步慢指针每次走一步 while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { return true; // 相遇说明有环 } } return false; // 快指针走到头了说明无环 }原理如果链表有环快指针最终会从后面追上慢指针就像在环形跑道上跑步一样。为什么快指针要走两步这是一个数学问题。设环外长度为a环长度为b。当慢指针进入环时快指针已经在环内。假设此时快指针落后慢指针c步0 c b。由于快指针每次比慢指针多走一步它们之间的距离每次减少1因此经过c次移动后它们必然相遇。4.2 寻找环的入口节点如果链表有环如何找到环的入口节点这是一个经典的面试题。ListNode *detectCycle(ListNode *head) { ListNode *slow head, *fast head; // 第一阶段判断是否有环并找到相遇点 while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) { // 相遇了 // 第二阶段寻找环入口 ListNode *ptr1 head; ListNode *ptr2 slow; // 从相遇点出发 while (ptr1 ! ptr2) { ptr1 ptr1-next; ptr2 ptr2-next; } return ptr1; // 环的入口 } } return nullptr; // 无环 }为什么第二阶段这样能找到入口这需要一点推导。沿用之前的符号环外长度a环长b相遇时慢指针走了s步快指针走了2s步。因为快指针比慢指针多走了n圈环所以2s s nbs nb。 相遇时慢指针走了nb步。一个关键点是从链表头走到环入口需要a步从环入口走到相遇点需要c步c是相遇点距离入口的步数。那么慢指针从起点到相遇点走过的路程s a nb c不对更准确的描述是慢指针从起点走到相遇点路程s a m其中m是慢指针在环内走的步数。而我们知道s nb。所以a m nba nb - m。nb - m意味着什么从相遇点出发再走a步相当于在环内走了nb - m m nb步也就是绕环n圈刚好回到相遇点这里需要更严谨的推导。实际上从相遇点走a步会到达环入口。因为a nb - m而从相遇点走nb步是绕环n圈回到原地所以走a步就相当于从相遇点“倒退”m步正好是环入口的位置。 更直观的理解是设ptr1从 head 出发ptr2从相遇点出发每次各走一步。当ptr1走完a步到达入口时ptr2也走了a步。而ptr2从相遇点走a步由于a nb - m相当于在环内走了nb步回到相遇点再倒退m步最终也到达了环入口。所以两者会在环入口相遇。经验之谈链表双指针问题中经常需要处理空指针。在移动fast fast-next-next之前务必先判断fast和fast-next是否为空。这是避免程序崩溃的基本功。5. 双指针处理字符串与子序列问题双指针在字符串匹配、子序列判断等问题上也非常高效它避免了不必要的回溯实现了线性时间的扫描。5.1 判断子序列问题给定字符串s和t判断s是否为t的子序列即s可以通过删除t中的一些字符得到且不改变剩余字符的相对位置。bool isSubsequence(string s, string t) { int i 0, j 0; // i指向sj指向t while (i s.size() j t.size()) { if (s[i] t[j]) { i; // 匹配成功移动s的指针 } j; // 无论是否匹配t的指针都向前移动 } // 如果s的所有字符都匹配完了说明s是t的子序列 return i s.size(); }逻辑我们用指针i追踪s的匹配进度指针j遍历t。只有当s[i]和t[j]相等时才说明s的第i个字符在t中找到了此时i前进一步。j则不断前进扫描t。如果最终i走到了s的末尾说明s的所有字符都在t中按顺序找到了。5.2 进阶通过删除字母匹配到字典里最长单词这是LeetCode 524题是子序列问题的变种。给定一个字符串s和一个字符串数组dictionary找出dictionary中最长的字符串该字符串可以通过删除s中的某些字符得到。如果答案不止一个返回字典序最小的。string findLongestWord(string s, vectorstring dictionary) { string result ; for (const string word : dictionary) { // 双指针判断word是否是s的子序列 int i 0; // 指向word for (char c : s) { // 遍历s if (i word.size() c word[i]) { i; } } // 如果word是子序列则判断是否更新结果 if (i word.size()) { if (word.size() result.size() || (word.size() result.size() word result)) { result word; } } } return result; }优化点上述解法在每次判断子序列时都完整遍历了字符串s复杂度为 O(n * m)其中 n 是s长度m 是字典中所有字符总数。一个常见的优化是预处理s。我们可以构建一个二维数组nextPos[i][c]表示从位置i开始包括i下一个字符c出现的位置。这样在匹配每个word时可以“跳跃式”地移动指针将每次匹配的复杂度降到 O(L)其中 L 是word的长度。这对于s很长、字典也很大的情况非常有效。// 预处理nextPos数组的示例代码框架 vectorvectorint buildNextPos(const string s) { int n s.size(); vectorvectorint nextPos(n 1, vectorint(26, -1)); // 从后向前构建 for (int i n - 1; i 0; --i) { nextPos[i] nextPos[i 1]; // 继承后一个位置的信息 nextPos[i][s[i] - a] i; // 更新当前字符的位置 } return nextPos; } // 使用nextPos进行匹配 bool isSubseqWithNext(const string word, const vectorvectorint nextPos) { int pos 0; // 在s中的当前位置 for (char c : word) { pos nextPos[pos][c - a]; if (pos -1) return false; pos; // 匹配成功移动到下一个位置开始查找 } return true; }6. 多指针与多序列问题当问题涉及到多个有序数组或链表时双指针的思想可以自然扩展到多指针。例如合并两个有序数组、寻找多个数组的交集、或者著名的“三数之和”问题。6.1 三数之和LeetCode 15. 三数之和给你一个整数数组nums判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j ! k且nums[i] nums[j] nums[k] 0。请你返回所有和为 0 且不重复的三元组。暴力解法是三重循环O(n³)。利用排序双指针可以优化到O(n²)。思路首先将数组排序。遍历数组将当前元素nums[i]作为三元组的第一个数。对于固定的i问题转化为在i之后的子数组中寻找两个数之和为-nums[i]。这就变成了一个标准的“两数之和”问题可以用左右指针解决。关键是如何去重。因为数组已排序重复的数字会相邻。我们需要跳过那些已经处理过的重复数字。vectorvectorint threeSum(vectorint nums) { vectorvectorint result; int n nums.size(); if (n 3) return result; sort(nums.begin(), nums.end()); // 关键步骤排序 for (int i 0; i n - 2; i) { // 去重如果当前数字和前一个相同跳过避免重复三元组 if (i 0 nums[i] nums[i - 1]) continue; int target -nums[i]; int left i 1, right n - 1; while (left right) { int sum nums[left] nums[right]; if (sum target) { result.push_back({nums[i], nums[left], nums[right]}); // 找到答案后需要跳过所有重复的left和right while (left right nums[left] nums[left 1]) left; while (left right nums[right] nums[right - 1]) --right; // 移动指针寻找下一组解 left; --right; } else if (sum target) { left; // 和太小左指针右移 } else { --right; // 和太大右指针左移 } } } return result; }为什么排序后双指针有效排序后当我们固定ileft从i1开始right从末尾开始。根据nums[left] nums[right]与target的比较我们可以安全地移动指针原理与“两数之和 II”完全相同。排序的代价是 O(n log n)但后续的双指针查找是 O(n)总体 O(n²)比暴力法好得多。极易出错点去重逻辑。必须在找到一组有效解之后再跳过重复的left和right。如果提前跳过可能会漏掉像[0,0,0]这样的合法解。同时对于外层循环的i去重判断是nums[i] nums[i-1]而不是nums[i] nums[i1]因为我们要保留第一个出现的数字作为候选跳过后续相同的。6.2 合并两个有序数组这是双指针或多指针最直观的应用之一。LeetCode 88题给你两个按非递减顺序排列的整数数组nums1和nums2另有两个整数m和n分别表示nums1和nums2中的元素数目。请你合并nums2到nums1中使合并后的数组同样按非递减顺序排列。nums1的空间足够大长度为mn。常见的思路是从前往后合并但这样需要额外的空间来暂存nums1的元素。一个更巧妙的做法是从后往前合并。void merge(vectorint nums1, int m, vectorint nums2, int n) { int p1 m - 1; // 指向nums1有效部分的末尾 int p2 n - 1; // 指向nums2的末尾 int p m n - 1; // 指向nums1整个空间的末尾 // 从后向前比较并放置 while (p1 0 p2 0) { if (nums1[p1] nums2[p2]) { nums1[p--] nums1[p1--]; } else { nums1[p--] nums2[p2--]; } } // 如果nums2还有剩余直接拷贝nums1剩余部分已经在正确位置 while (p2 0) { nums1[p--] nums2[p2--]; } // 如果nums1有剩余它们已经在正确位置无需处理 }为什么从后往前因为nums1的后半部分是空闲的从后往前填充可以避免覆盖nums1前半部分尚未处理的元素。这是一个“原地”操作的经典技巧。7. 复杂场景下的指针移动策略与边界处理双指针的难点往往不在于理解算法本身而在于确定指针移动的条件和处理各种边界情况。下面通过几个复杂例子来深入探讨。7.1 盛最多水的容器LeetCode 11题给你n个非负整数a1, a2, ..., an每个数代表坐标中的一个点(i, ai)。找出其中两个线使得它们与 x 轴共同构成的容器可以容纳最多的水。暴力法是枚举所有可能的左右挡板组合计算面积。双指针如何优化 初始时左右指针分别指向数组两端。容器的盛水量由较短挡板的高度和两板之间的距离决定area min(height[left], height[right]) * (right - left)。 直觉告诉我们为了获得更大的面积我们希望高度和宽度都尽可能大。由于宽度初始最大我们移动指针时宽度必然减小。因此为了有可能获得更大的面积我们必须尝试增加高度。而高度由较短的挡板决定所以我们应该移动较短的那一侧的指针希望能找到一个更高的挡板。int maxArea(vectorint height) { int left 0, right height.size() - 1; int maxWater 0; while (left right) { int h min(height[left], height[right]); int w right - left; maxWater max(maxWater, h * w); // 关键决策移动矮的那一边 if (height[left] height[right]) { left; } else { --right; } } return maxWater; }正确性证明假设当前左右指针为i和j且height[i] height[j]。如果我们移动较高的j到j-1新的宽度w减小了。新的高度h min(height[i], height[j-1])。由于height[i]是原来较短的height[j-1]可能比height[i]高或低但h最大也不会超过height[i]即原来的h。所以新面积area h * w一定小于原来的面积h * w因为h h且w w。因此移动高板不可能得到更大的面积。反之移动矮板i虽然宽度也减小了但高度有可能增加如果height[i1] height[i]从而可能得到更大的面积。这个决策保证了我们不会错过最优解。7.2 统计「优美子数组」LeetCode 1248题给你一个整数数组nums和一个整数k。如果某个连续子数组中恰好有k个奇数数字我们就认为这个子数组是「优美子数组」。请返回这个数组中「优美子数组」的数目。这个问题可以用滑动窗口结合前缀和思想来解决但指针移动策略需要仔细设计。一个直观但低效的方法是枚举所有子数组并统计奇数个数。优化思路是我们只关心奇数的位置。int numberOfSubarrays(vectorint nums, int k) { int n nums.size(); vectorint oddIndices; // 记录所有奇数元素的下标 oddIndices.push_back(-1); // 添加一个虚拟左边界方便计算 for (int i 0; i n; i) { if (nums[i] % 2 1) { oddIndices.push_back(i); } } oddIndices.push_back(n); // 添加一个虚拟右边界 if (oddIndices.size() - 2 k) return 0; // 奇数总数不足k个 int count 0; // 现在oddIndices里存储了所有奇数的索引以及边界-1和n // 我们需要一个大小为k的窗口在oddIndices上滑动 for (int i 1; i k oddIndices.size(); i) { int left oddIndices[i]; // 窗口内第1个奇数的位置 int right oddIndices[i k - 1]; // 窗口内第k个奇数的位置 // 窗口左边可以扩展的位置数从上一个奇数之后到left int leftChoices left - oddIndices[i - 1]; // 窗口右边可以扩展的位置数从right到下一个奇数之前 int rightChoices oddIndices[i k] - right; // 左右扩展的选择是独立的所以相乘 count leftChoices * rightChoices; } return count; }思路解析我们并不直接在原数组上滑动窗口而是先在奇数索引数组oddIndices上维护一个固定大小为k的窗口。对于oddIndices中的每一个长度为k的连续段[oddIndices[i], oddIndices[ik-1]]它对应了原数组中一个核心的优美子数组恰好包含这k个奇数。这个核心子数组可以向左右两侧扩展只要不包含新的奇数即可。向左可以扩展到oddIndices[i-1] 1向右可以扩展到oddIndices[ik] - 1。因此以这个核心段为基础的优美子数组总数为(leftChoices) * (rightChoices)。这种方法将问题转化为了在奇数索引数组上的简单遍历复杂度为 O(n)。8. 调试技巧与常见陷阱实录即使理解了算法实现时也难免踩坑。下面是我在大量练习中总结出的几个关键陷阱和调试方法。8.1 指针越界与空指针这是双指针问题中最常见的运行时错误。链表问题在访问fast-next-next之前必须确保fast和fast-next不为nullptr。数组问题在移动left或right指针时要确保它们始终在有效索引范围内[0, size()-1]。特别是在while循环的条件中检查顺序很重要。例如while (left right nums[left] nums[left-1])必须先检查left right否则left-1可能越界。防御性编程习惯在移动指针前先思考“移动后指针会变成什么它有效吗”对于链表可以多写几个临时变量来增加可读性和安全性。8.2 循环终止条件模糊什么时候该用while (left right)什么时候用while (left right)这取决于你对区间的定义。左闭右开区间[left, right)通常right初始化为nums.size()循环条件为while (left right)更新时right mid二分查找中常见。左闭右闭区间[left, right]通常right初始化为nums.size() - 1循环条件为while (left right)。 在双指针中我推荐统一使用左闭右闭区间即left和right都指向有效元素循环条件为while (left right)或根据问题调整为while (left right)。关键是要在整个算法中保持一致。8.3 去重逻辑错误在“三数之和”、“四数之和”等问题中去重是难点。一个黄金法则是去重操作应该在找到一组有效解之后进行并且要同时跳过所有重复的元素。例如在三数之和中if (sum target) { result.push_back(...); // 去重跳过所有与当前left/right相同的值 while (left right nums[left] nums[left1]) left; while (left right nums[right] nums[right-1]) right--; // 然后移动指针到下一个不同的元素 left; right--; }如果先去重再添加结果会漏掉[a, a, a]这种组合当3*a target时。8.4 整数溢出在计算乘积、和或者距离时要特别注意数据范围。例如在“乘积小于K的子数组”中product用int很容易溢出即使题目说nums[i] 1000但连续乘几十个数就可能超出int范围。稳妥的做法是使用long long。在“盛水容器”问题中面积计算h * w也可能溢出虽然LeetCode的用例可能不会但在工业级代码中应该考虑使用long long或提前判断。8.5 滑动窗口收缩条件不清滑动窗口的难点在于确定内层while循环的收缩条件。一个有用的思考框架是定义窗口状态明确窗口[left, right)需要维护什么信息和、积、不同字符数等。定义目标窗口状态需要满足什么条件例如sum k,product k, 字符种类数 2。确定收缩时机当窗口状态不满足目标时需要收缩窗口。但有时我们需要的是“满足条件时的最短窗口”那么收缩条件就是“当窗口状态仍然满足目标时尝试收缩以找到更优解”。求最短满足条件的窗口内层用while (窗口状态满足条件) { 更新答案收缩左边界}求最长满足条件的窗口内层用while (窗口状态不满足条件) { 收缩左边界}并在外层更新答案。如果实在想不清楚可以在纸上画一个例子手动模拟指针移动过程这是调试双指针问题最有效的方法。双指针技巧的精髓在于利用数据本身的特性有序性、单调性来减少不必要的计算。它要求我们对问题有深刻的理解能够抽象出指针移动的“单调”依据。掌握它没有捷径多练习、多总结、多模拟直到你能在看到问题描述时脑海中自然浮现出两个指针如何移动的画面。当你达到这个境界很多中等难度的算法题都将迎刃而解。