Keep Theme
算法学习-玩转双指针
Keep Team Lv4
  2026-02-25 15:23:08   2026-02-25 21:20:06

​ 如果说哈希表是用空间换取时间的典范，那么双指针则是将“状态压缩”与“线性扫描”结合得最完美的艺术。在 LeetCode 的高频面试题中，双指针的身影无处不在——从经典的“两数之和”到复杂的“接雨水”问题，它通过巧妙地维护两个索引之间的不变量，避免了冗余计算，实现了极致的效率。然而，很多学习者往往只记住了模板，却没能参透其背后“何时移动左指针、何时移动右指针”的判断逻辑。本文旨在跳出单纯的代码背诵，通过分类剖析与实战演练，带你真正看透双指针的本质，做到举一反三，玩转算法。

下面介绍双指针经典模式：

1.左右对撞双指针

1.1 两数之和

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

题解

初始时两个指针分别指向第一个元素和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。

  • 如果两个元素之和等于目标值，则发现唯一解。
  • 如果两个元素之和小于目标值，则将左侧指针右移一位
  • 如果两个元素之和大于目标值，则将右侧指针左移一位

直到找到答案

1
2
3
4
5
6
7
8
9
10
11
vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0;
    int 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};
}

1.2 盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

image-20260225211508545

题解

在初始时，左右指针分别指向数组的左右两端，它们可以容纳的水量为 min(1,7)∗8=8。

此时我们需要移动一个指针。移动哪一个呢？直觉告诉我们，应该移动对应数字较小的那个指针（即此时的左指针）。这是因为，由于容纳的水量是由两个指针指向的数字中较小值∗指针之间的距离
决定的。如果我们移动数字较大的那个指针，那么前者「两个指针指向的数字中较小值」不会增加，后者「指针之间的距离」会减小，那么这个乘积会减小。因此，我们移动数字较大的那个指针是不合理的。因此，我们移动 数字较小的那个指针。

所以，我们将左指针向右移动：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
此时可以容纳的水量为 min(8,7)∗7=49。由于右指针对应的数字较小，我们移动右指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
此时可以容纳的水量为 min(8,3)∗6=18。由于右指针对应的数字较小，我们移动右指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
此时可以容纳的水量为 min(8,8)∗5=40。两指针对应的数字相同，我们可以任意移动一个，例如左指针：

[1, 8, 6, 2, 5, 4, 8, 3, 7]
^ ^
此时可以容纳的水量为 min(6,8)∗4=24。由于左指针对应的数字较小，我们移动左指针，并且可以发现，在这之后左指针对应的数字总是较小，因此我们会一直移动左指针，直到两个指针重合。在这期间，对应的可以容纳的水量为：min(2,8)∗3=6，min(5,8)∗2=10，min(4,8)∗1=4。

在我们移动指针的过程中，计算到的最多可以容纳的数量为 49，即为最终的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maxArea(vector<int>& height) {
    int left,right,area;
    left = 0;
    right = height.size()-1;
    int ans = 0;
    while(left < right){
        area = (right - left) * min(height[left],height[right]);
        ans = max(ans, area);

        if(height[left] < height[right]){
            left++;
        }else{
            right--;
        }
    }
    return ans;
}