双指针算法全解析：从暴力枚举到O(N)的思维跃迁

happy最紧要

212人浏览 · 2026-09-12 12:16:15

happy最紧要 · 2026-09-12 12:16:15 发布

算法面试里有两类题让我印象最深刻，一类是动态规划，状态转移想不出来就是死活想不出来，另一类就是双指针。双指针这名字听起来简单，不就是两个下标吗，但很多人在 LeetCode 上刷了两三百题，遇到双指针的变体还是会懵。原因在于双指针不是一个“知识点”，而是一整套“利用坐标关系省掉暴力枚举”的思维方式。把这种思维吃透，像两数之和、最长无重复子串、环形链表、盛最多水的容器这些题，全部可以从同一个底层逻辑推出来。

这篇专题我重点讲三件事:双指针为什么能让 O(N²) 变成 O(N)、三类最常见指针模型的适用场景和代码套路、以及我在实际刷题和笔试里踩过的边界坑。内容偏向实战，每一段都会配题和代码，不搞虚的。

1. 双指针到底解决了什么问题:从暴力枚举到坐标单调性

先说我自己的体会。大一学算法的时候，老师讲两数之和，我的第一反应肯定是两层 for 循环，O(N²)，简单直接。后来刷题多了才发现，几乎所有双指针题目的出发点都是:暴力解法太慢，而慢的原因在于我们枚举了大量“不可能成立”的组合。

1.1 复杂度困境从哪来

假设数组长度是 N，暴力双层循环需要比较 N×(N-1)/2 对组合，也就是 O(N²)。当 N 是 10⁵ 量级，O(N²) 大概是 10¹⁰ 次操作，稳定超时。双指针的思路不是减少常数，而是通过某种“单调关系”，让两个指针在遍历过程中总共只移动 O(N) 次。

这句话很关键。双指针之所以快，不是因为用了什么黑科技，而是因为 我们通过排序或预处理，让候选答案的搜索空间可以沿着一个方向单调收缩 。每一次移动指针，都排除了一个区间，而不是排除一个点。

1.2 用一个例子理解“排除区间”

拿有序数组的两数之和来举例。数组 [1, 3, 5, 7, 9] ，目标值 12。

暴力法:固定第一个数，挨个试第二个数。
双指针法:左指针 L 在 1，右指针 R 在 9，1+9=10 小于 12。因为数组是递增的，L 右边任何一个数都比 1 大，但 R 已经是最大的了，所以此时不是去移动 R，而是 只有移动 L 这一条路 。于是 L 移到 3，3+9=12，命中。

注意刚才这一步:当 1+9 小于目标值时，9 与 1 左边所有数的组合都不可能成立吗?不对，此时 L 已经在最左边了。更准确的说法是:1 与 9 右边任意数的组合也不可能成立，因为 9 右边没有数了;但 1 与 9 左边的数的组合已经全试过了。其实最核心的判断是:当 1+9<12，说明 1 和当前最大值的和都小于目标，那么 1 和任何更小的数相加只会更小，所以 1 这个数可以直接排除 ，L 向右移动。同理，如果 L+R>目标值，说明 R 和当前最小值的和都大于目标，R 与任何更大的数相加只会更大，所以 R 可以直接排除。

每一步至少排除一个元素，总共最多 N 步，所以复杂度是 O(N)。双指针的全部秘密，就在这种“排除区间”的推理里。

1.3 双指针的三个关键词

根据我的经验，判断一道题能不能用双指针，就看三个词: 有序性 、 单调性 、 边界收缩 。

有序性:数组本身排序，或者经过排序后保证某种顺序。
单调性:随着指针移动，某个函数值（和、积、窗口长度）单调变化。
边界收缩:问题要求可以从两端或同向收缩搜索区间。

如果一道题满足这三条，大概率可以用双指针。如果不满足，硬套双指针很容易出错。这个判断方法在我刷题前中期帮我少走了很多弯路。

2. 相向双指针：有序数组的左右夹逼套路

相向双指针也叫对撞指针，两个指针一个在左端、一个在右端，不断向中间移动。它最适合的题目类型是“在有序数组里找满足某种条件的元素组合”。

2.1 两数之和 II:最标准的相向模板

LeetCode 167 是相向双指针的入门题。给定已按升序排列的数组，找到两个数使它们的和等于目标值。

vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) return {left + 1, right + 1};
        else if (sum < target) left++;
        else right--;
    }
    return {-1, -1};
}

这里我特别想强调 while 条件用的是 left < right 而不是 left <= right 。因为两个数不能是同一个元素，所以当 left==right 时循环应该结束。很多初学的朋友在这里写成 <=，结果在某些用例下返回了同一个下标，排查半天。

还有一个细节:题目要求返回的下标从 1 开始，所以返回 left+1 和 right+1 。这种“输出格式的坑”笔试里经常出现，不看题目要求直接返回 left 和 right，大概率错。

2.2 三数之和:相向指针加去重

三数之和是两数之和的升级版。给定数组，找出所有三元组，使得三个数之和为 0，且不重复。

思路是固定一个数，然后用双指针找剩下两个数。但麻烦在于去重。我第一遍写这个题的时候，用了一个 set 去重，AC 了，但复杂度多了个 log。后来才发现，排序之后可以直接在指针移动时跳过重复元素，根本不需要 set。

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    for (int i = 0; i < n - 2; i++) {
        if (nums[i] > 0) break; // 因为数组有序，第一个数大于0就不用继续了
        if (i > 0 && nums[i] == nums[i-1]) continue; // 跳过重复的第一个数
        int left = i + 1, right = n - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (sum == 0) {
                res.push_back({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 res;
}

这里的去重逻辑很有意思。外层循环跳过重复的 nums[i]，内层找到一组答案后也要跳过重复的左右指针值。注意内层跳过的时机:必须是在找到一个答案之后。如果在进入循环前就跳过重复值，会漏掉一些组合。这个顺序问题我踩过坑:先跳过后找答案，结果 [-1,-1,2] 这种组合被跳没了。核心原则是: 去重针对的是已经处理过的值，而不是还没处理的值 。

2.3 盛最多水的容器:贪心式移动

这题是相向双指针里最考验理解的一道。给定一组垂直线的高度，找两条线与 x 轴组成容器，能装最多水。

容器的水量是 min(height[left], height[right]) * (right - left) 。暴力是 O(N²)，双指针做是 O(N)。

核心逻辑:每次移动高度较小的一侧指针。为什么?因为水量受限于矮的那根柱子。如果移动高的那根，宽度减小，高度还是受矮的约束，水量不可能增加。只有移动矮的那根，才有可能遇到更高的柱子，从而提升水量上限。

int maxArea(vector<int>& height) {
    int left = 0, right = height.size() - 1;
    int ans = 0;
    while (left < right) {
        int area = min(height[left], height[right]) * (right - left);
        ans = max(ans, area);
        if (height[left] < height[right]) left++;
        else right--;
    }
    return ans;
}

这个移动策略其实是一种贪心。你每一次移动都舍弃了一部分可能解，但你可以证明:被舍弃的那些解不可能比当前已知的最优解更好。这样的证明能力，比背代码重要得多。

3. 同向双指针：滑动窗口的边界艺术

同向双指针，俗称滑动窗口，两个指针都从左往右走，维护一个窗口区间。它适合处理“连续子数组/子串”类的问题，比如最长、最短、固定长度满足某种条件的区间。

3.1 滑动窗口的标准模板

我总结的滑动窗口模板是四步走:

右指针不断右移，扩大窗口，更新窗口内状态。
当窗口不满足约束条件时，左指针右移，缩小窗口。
每轮更新答案。
右指针到达数组末尾后结束。

# 伪代码模板
left = 0
for right in range(len(nums)):
    # 1. 更新窗口状态
    window.add(nums[right])
    # 2. 收缩窗口
    while left <= right and not valid(window):
        window.remove(nums[left])
        left += 1
    # 3. 更新答案
    ans = max(ans, right - left + 1)

这里的核心是“窗口状态”的定义。不同的题，窗口状态可以是字符频率、独特性、数值和等等。 只要你能快速判断窗口是否合法，滑动窗口就能用。

3.2 无重复字符的最长子串

LeetCode 3，经典中的经典。给定一个字符串，找出不含重复字符的最长子串长度。

窗口状态用哈希集合维护当前窗口内的字符。右指针不断扩，如果发现新字符已经在集合里，就移动左指针直到移除重复字符。

int lengthOfLongestSubstring(string s) {
    unordered_set<char> window;
    int left = 0, ans = 0;
    for (int right = 0; right < s.size(); right++) {
        while (window.count(s[right])) {
            window.erase(s[left]);
            left++;
        }
        window.insert(s[right]);
        ans = max(ans, right - left + 1);
    }
    return ans;
}

这里有个小陷阱:while 循环里移动左指针时，不是直接删除当前右指针的字符，而是从左侧一个一个删，直到把重复的字符删出去。不少新手会直接 window.erase(s[right]) ，这是错的，因为重复字符可能在窗口中间，直接删除会丢掉信息。

3.3 最小覆盖子串:窗口收缩的进阶用法

这题比上一题难一个档次:给定字符串 S 和 T，在 S 中找到包含 T 全部字符的最小窗口。

需要维护一个 need 计数数组和一个已匹配计数。当窗口内已经包含 T 中所有字符时，尝试收缩左边界，找到最短的满足条件的窗口。

string minWindow(string s, string t) {
    vector<int> need(128, 0), have(128, 0);
    for (char c : t) need[c]++;
    int left = 0, cnt = 0;
    int minLen = INT_MAX, start = 0;
    for (int right = 0; right < s.size(); right++) {
        char c = s[right];
        if (need[c]) {
            have[c]++;
            if (have[c] <= need[c]) cnt++;
        }
        while (cnt == t.size()) {
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                start = left;
            }
            char lc = s[left];
            if (need[lc]) {
                if (have[lc] <= need[lc]) cnt--;
                have[lc]--;
            }
            left++;
        }
    }
    return minLen == INT_MAX ? "" : s.substr(start, minLen);
}

这段代码刚才我压缩过，完整版最好带上注释。核心是 cnt == t.size() 表示窗口已经覆盖了 T 中所有字符。移动左指针时，如果左边出去的字符是 T 需要的，而且出去后拥有数小于需要数，说明匹配数量减少，cnt 减一。

这个题我建议每个认真学双指针的人都独立写一遍，因为它涵盖了两个窗口操作方向的所有细节:扩大窗口时更新状态、收缩窗口时更新状态、每次收缩后都尝试更新答案。

4. 快慢指针:链表里的“龟兔赛跑”

快慢指针是一个很容易被忽略的分类，因为它不走数组的下标，而是操作链表节点。一个指针每次走一步，另一个每次走两步，利用速度差来达到“定位”或“判圈”的目的。

4.1 链表的中间节点

一个很直接的场景:给定链表头，找出中间节点。快指针每次走两步，慢指针每次走一步，快指针到末尾时，慢指针刚好在中间。

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

这里 while 条件 fast && fast->next 是必须的，因为快指针每次走两步，如果 fast 为空或者 fast->next 为空，都不能继续。条件顺序不能反，要先判断 fast 不为空再判断 fast->next，否则访问空指针会崩。

4.2 Floyd 判圈算法

判断链表是否有环，最常见的做法就是快慢指针。如果有环，快指针最终会追上慢指针，两者相遇。

bool hasCycle(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

为什么快慢指针一定能相遇?这个证明很有意思。假设环的长度为 L，当慢指针进入环时，快指针已经在环内某个位置。因为快指针比慢指针快一步，每走一次相对距离缩短 1，所以最多走 L-1 步后必定追上。这其实就是小学奥数里的追及问题。

4.3 环形链表 II:找到环的入口

进阶版:不仅要判断有环，还要找到环的入口节点。

这里有一个数学结论:快慢指针相遇后，让一个指针从头开始走，另一个指针从相遇点开始走，两者每次都走一步，再次相遇的位置就是环的入口。

证明:设头到环入口距离为 a，入口到相遇点距离为 b，相遇点绕回入口距离为 c。慢指针走了 a+b，快指针走了 a+b+L(即一圈环的长度又加 b)。因为快指针速度是慢指针两倍，所以 2(a+b)=a+b+a+b，化简得到 a+b = L-b，即 a = L-b = c。所以从头出发的指针和从相遇点出发的指针会在入口再次相遇。

ListNode* detectCycle(ListNode* head) {
    ListNode* slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;
}

这个数学推导我建议自己画图推一遍，不然真的容易忘。背代码的缺点是换一个数字、换一种问法你就懵了，但懂了推导，无论题目怎么变形都能应付。

5. 实战中踩过的坑:边界、去重与死循环

前面讲的是方法论和模板，这一节我想专门说说实战里最容易翻车的几个地方。这些都是我在刷题和实际笔试里真实踩过的坑，写出来给大家避雷。

5.1 重复元素跳过时机的错判

三数之和里的去重顺序问题，我刚才已经强调过一次。这里再补充一个更隐蔽的坑:有些题先排序再去重，但排序后原始下标丢失。如果题目要求返回的是元素值而不是下标，一般没问题;如果要求返回下标，排序这条路就堵死了，得用哈希表做两数之和。所以做双指针题之前先问自己:这题能不能排序?排序会不会破坏我需要的答案形式?

5.2 区间边界到底是 `<` 还是 `<=`

这是双指针新手最容易晕的地方。我总结了一条经验:

如果左右指针指向的是同一个元素时没有意义（比如两数之和、三数之和），用 left < right 。
如果滑动窗口允许窗口为空（比如最小覆盖子串中窗口可以收缩到空），左指针可能大于右指针，循环条件要仔细推导。
如果是二分查找的变体，通常是 left <= right 。

具体实现时，我推荐先在纸上画出 left 和 right 的移动路径，手动跑一个长度 2 的用例，基本能确认边界条件是否写对。

5.3 快慢指针的死循环风险

快慢指针代码看起来简单，但有个常见的坑:在 while 循环里没有判断 fast 是否为空就访问 fast->next->next，导致空指针异常。有些语言直接崩，有些语言返回错误结果。我的习惯是每个循环入口都写 while (fast && fast->next) ，在循环体里绝对不假设 fast 或 fast->next 非空。

还有一个跟死循环相关的场景:Floyd 判圈算法中，如果链表没有环，fast 会先到达末尾，此时循环自然结束;如果有环，while 条件里的 fast 永远非空，循环会一直执行直到 slow 和 fast 相遇。这个逻辑是安全的，不存在死循环。但如果你在循环里忘了移动 slow，或者移动步数写错，就可能让 fast 一次又一次地越过 slow，永远不相遇。步数写对很重要。

5.4 滑动窗口的状态更新遗漏

滑动窗口最容易出的 bug 是:窗口扩大时更新了状态，但窗口收缩时没有同步撤销状态，或者反过来。最小覆盖子串那个题，我在左指针移动时忘了对 have 数组做减一操作，结果窗口收缩后状态仍然认为字符存在，答案直接算错。这类 bug 很难查，因为代码逻辑完全说得通，就是状态不同步。我后来写滑动窗口都用“扩大一步、同步状态、收缩一步、同步状态”这样的节奏来写，每次操作前后状态必须一致。

5.5 数组元素为负数的陷阱

很多双指针题目默认数组是正数，但一旦出现负数，滑动窗口的收缩条件就要重新考虑。比如“和等于 k 的最短连续子数组”，如果数组有负数，窗口内的和就不是单调的了，滑动窗口直接失效，只能用前缀和加哈希表或者更复杂的做法。所以拿到题目先看数据范围，有没有负数，有没有重复值，这些直接决定了双指针能不能用。

6. 双指针与其他算法的组合套路

双指针很少孤立出现，它经常和排序、二分、贪心等算法配合，形成综合性题目。这一节我梳理几个常见的组合模式。

6.1 双指针 + 排序:先排序再夹逼

最经典的当然还是三数之和、四数之和。排序的目的就是让数组获得单调性，这样双指针的移动才有依据。如果题目允许修改原数组，排序几乎是免费的。

四数之和是三数之和的扩展，固定前两个数，剩下两个用双指针。去重逻辑比三数之和更复杂，因为有两层固定循环都要去重。写这类题时我建议先写三数之和，再扩展到四数之和，不要一上来就硬写四层。

vector<vector<int>> fourSum(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    for (int i = 0; i < n - 3; i++) {
        if (i > 0 && nums[i] == nums[i-1]) continue;
        for (int j = i + 1; j < n - 2; j++) {
            if (j > i + 1 && nums[j] == nums[j-1]) continue;
            long long need = (long long)target - nums[i] - nums[j];
            int left = j + 1, right = n - 1;
            while (left < right) {
                long long sum = (long long)nums[left] + nums[right];
                if (sum == need) {
                    res.push_back({nums[i], nums[j], 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 < need) left++;
                else right--;
            }
        }
    }
    return res;
}

注意这里我把 sum 和 need 强转成了 long long，因为四数之和的中间结果可能超过 int 范围。这类细节在 LeetCode 上可能不触发，但在面试或者笔试的用例里很容易翻车。

6.2 双指针 + 二分:用单调性优化

有些双指针题其实是二分的变体。比如“找最接近目标的三个数之和”，可以先排序，固定一个数，再用双指针找最接近 target 的剩下两个数。这种题的核心还是双指针，但如果你对双指针理解不深，也可以退化为固定一个数后对另外两个数做二分查找。

我个人的观点是:能双指针就不二分，因为双指针 O(N) 比二分 O(N log N) 快。但有些题没法双指针时，二分是好备胎。

6.3 双指针 + 贪心:跳跃游戏 II

跳跃游戏 II 是一道贪心题，但很多题解里也用到了“双指针”的思想。维护当前跳跃能达到的最远位置和下一跳能达到的最远位置，遍历数组时用两个边界来分段。

int jump(vector<int>& nums) {
    int n = nums.size(), ans = 0;
    int curEnd = 0, curFarthest = 0;
    for (int i = 0; i < n - 1; i++) {
        curFarthest = max(curFarthest, i + nums[i]);
        if (i == curEnd) {
            ans++;
            curEnd = curFarthest;
        }
    }
    return ans;
}

这里 curEnd 和 curFarthest 就是两个指针，只是它们不是像数组双指针那样一左一右，而是分别代表当前层的终点和下一层的最远点。很多同学没想到贪心题也能用双指针思想，但本质上它们都在做一件事: 用两个坐标值维护一个可行的边界范围，逐步推进答案。