迎风起降的小站
双指针
蜂窝煤 Lv3
  2026-08-31 17:03:28   2026-09-22 14:53:05    

双指针是一种通过两个指针协同移动，减少重复遍历的算法技巧，常用于数组、字符串和链表问题。

基本思路

根据两个指针的移动方向和作用，双指针通常可以分为以下几类：

  • 左右指针：两个指针分别从区间两端向中间移动，常用于有序数组、回文判断和区间搜索。 while left < right。
  • 快慢指针：两个指针从同一位置出发，以不同速度移动，常用于链表判环、寻找中点和原地删除元素。for fast in range(len(nums))。
  • 同向指针：两个指针都从左向右移动，通过维护窗口或区间处理连续子数组、子串问题。

题目索引

题号 题目 难度
283 移动零 简单
11 盛最多水的容器 中等
15 三数之和 中等
42 接雨水 困难

题目记录

移动零

题号：283
难度：简单

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

示例

示例 1：

1
2
输入：nums = [0,1,0,3,12]
输出：[1,3,12,0,0]

示例 2：

1
2
输入：nums = [0]
输出：[0]

提示

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

思路

原始思路 $O(n^2)$

原始写法使用两个指针：slow 指向当前需要处理的位置，fast 向后查找下一个非零数字。

  • 如果 nums[slow] 不为 0，说明当前位置已经正确，slow 向后移动，同时将 fast 重置到 slow + 1。
  • 如果 nums[slow] 和 nums[fast] 都为 0，则继续向后移动 fast。
  • 如果 nums[slow] 为 0 且 nums[fast] 不为 0，则交换两个位置的元素。

这种写法的缺点是，slow 每次遇到非零数字后，fast 都会被重置，之前扫描过的元素可能被重复扫描。因此，最坏情况下时间复杂度可能退化为 $O(n^2)$，空间复杂度为 $O(1)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from typing import List


class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow = 0
        fast = 1

        while slow < fast < len(nums):
            if nums[slow] != 0:
                slow += 1
                fast = slow + 1
                continue

            if nums[fast] == 0:
                fast += 1
                continue

            nums[slow], nums[fast] = nums[fast], nums[slow]

优化思路 $O(n)$

使用快慢指针完成原地移动：slow 维护下一个非零数字应该放置的位置，也可以理解为 nums[0:slow] 都是已经完成放置的区间；fast 则从头到尾扫描数组，只前进不后退。

每当 fast 扫描到一个非零数字，就交换 nums[slow] 和 nums[fast]，交换完成后再将 slow 向后移动一位。

这种写法不会产生 slow 追上 fast 后无法处理的问题：fast 每轮循环都会向前移动，而 slow 只有在发现非零数字并完成交换后才会向前移动。

例如数组 [5,1,0,6] 的初始状态为 slow = 0。前两个非零数字分别与自身交换，数组内容不变，但 slow 和 fast 同步向后移动。fast 扫描到 0 时，slow 因为没有产生交换，所以 slow 停留在 0 ，作为下一个待填充位置；fast 扫描到 6 时，将 nums[2] 和 nums[3] 交换，最终得到 [5,1,6,0]。

空间复杂度为 $O(1)$。

优化解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
from typing import List


class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        slow = 0

        for fast in range(len(nums)):
            if nums[fast] != 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1

盛最多水的容器

题号：11
难度：中等

题目描述

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

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

说明： 你不能倾斜容器。

示例

示例 1：

image

1
2
3
输入：height = [1,8,6,2,5,4,8,3,7]
输出：49
解释：图中蓝色部分表示容器能够容纳的水，最大值为 49。

示例 2：

1
2
输入：height = [1,1]
输出：1

提示

  • n == height.length
  • 2 <= n <= 10^5
  • 0 <= height[i] <= 10^4

思路 $O(n)$

容器的面积等于底边宽度乘以两条边中较短的高度：

$$
area = (right - left) \times \min(height[left], height[right])
$$

因此，使用左右指针分别指向数组两端。初始状态下，两个指针之间的距离最大，容器的宽度也最大。

每次计算当前面积后，移动高度较短的一侧：

  • 如果移动高度较高的一侧，宽度会减小，而较短的一侧仍然存在，容器高度不可能提高，面积一定不会变大。
  • 移动高度较短的一侧，虽然宽度减少了 1，但有机会找到更高的柱子，从而提高容器的高度，这是面积变大的唯一可能。

所以，每轮只需要移动较短的一侧，并持续更新最大面积。当左右指针相遇时，所有可能的边界组合都已经被排除，算法结束。

空间复杂度为 $O(1)$。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from typing import List


class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        max_area = 0

        while left < right:
            current_area = (right - left) * min(height[left], height[right])
            max_area = max(current_area, max_area)

            if height[left] <= height[right]:
                left += 1
            else:
                right -= 1

return max_area

三数之和

题号：15
难度：中等

题目描述

给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]]，满足 i != j、i != k 且 j != k，同时还满足 nums[i] + nums[j] + nums[k] == 0。请你返回所有和为 0 且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例

示例 1：

1
2
3
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：不同的三元组是 [-1,0,1] 和 [-1,-1,2]。

示例 2：

1
2
3
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0。

示例 3：

1
2
3
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0。

提示

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

思路 $O(n^2)$

三数之和可以拆解为两数之和：先固定一个数 nums[i]，再在它后面的区间中寻找两个数，使它们的和等于 -nums[i]。

首先对数组进行排序。排序的时间复杂度为 $O(n \log n)$，而固定一个数后使用左右指针寻找另外两个数的时间复杂度为 $O(n^2)$，因此排序不会改变整体的最优时间复杂度，整体仍为 $O(n^2)$。

排序后，左指针指向区间的左侧，右指针指向区间的右侧：

  • 如果 nums[left] + nums[right] 大于 -nums[i]，说明当前和太大，应将右指针左移。
  • 如果 nums[left] + nums[right] 小于 -nums[i]，说明当前和太小，应将左指针右移。
  • 如果两者相等，就找到一个符合条件的三元组。

集合与元组去重 $O(n^2)$

这是使用集合与元组进行去重的版本。找到符合条件的三元组后，将其转为元组并加入集合 results，利用集合中元素不能重复的特性去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums_sort = sorted(nums)
        results = set()

        # 拆解成两数之和，先固定一个数
        for i in range(len(nums_sort)):
            # 需要找到两个数和为 -nums_sort[i]
            left = i + 1
            right = len(nums_sort) - 1
            while left < right:
                if nums_sort[left] + nums_sort[right] == -nums_sort[i]:
                    results.add(tuple([nums_sort[i], nums_sort[left], nums_sort[right]]))
                    left += 1
                elif nums_sort[left] + nums_sort[right] > -nums_sort[i]:
                    right -= 1
                    continue
                else:
                    left += 1
                    continue
        return [list(t) for t in results]

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$；其中结果集合可能保存 $O(n^2)$ 个三元组，排序产生的辅助数组占用 $O(n)$ 空间。

双指针去重 $O(n^2)$

去重包含两个部分：一个是对固定数的去重，另一个是对左右指针对应数字的去重。

当固定数与前一个数相同时，跳过本轮，避免重复寻找相同的三元组。找到一组符合条件的结果后，同时移动左右指针，并跳过连续的重复数字，这样就可以在不借助集合的情况下完成去重。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        nums_sort = sorted(nums)
        results = []

        # 拆解成两数之和，先固定一个数
        for i in range(len(nums_sort)):
            if i >= 1 and nums_sort[i] == nums_sort[i - 1]:
                continue

            # 需要找到两个数和为 -nums_sort[i]
            left = i + 1
            right = len(nums_sort) - 1
            while left < right:
                if nums_sort[left] + nums_sort[right] == -nums_sort[i]:
                    results.append([nums_sort[i], nums_sort[left], nums_sort[right]])
                    left += 1
                    right -= 1

                    while left < right and nums_sort[left] == nums_sort[left - 1]:
                        left += 1
                    while left < right and nums_sort[right] == nums_sort[right + 1]:
                        right -= 1
                elif nums_sort[left] + nums_sort[right] > -nums_sort[i]:
                    right -= 1
                    continue
                else:
                    left += 1
                    continue
        return results

时间复杂度为 $O(n^2)$，空间复杂度为 $O(n^2)$；其中 $O(n^2)$ 的空间主要用于保存返回结果，除结果外的额外空间复杂度为 $O(n)$。

哈希表版本请参考：哈希算法：三数之和。

接雨水

题号：42
难度：困难

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子下雨之后可以接多少雨水。

示例

示例 1：

image

1
2
3
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面的高度图由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示，可以接 6 个单位的雨水。

示例 2：

1
2
输入：height = [4,2,0,3,2,5]
输出：9

提示

  • n == height.length
  • 1 <= n <= 2 * 10^4
  • 0 <= height[i] <= 10^5

思路

首先改变思路：不再直接计算每个坑能装多少水，而是计算每个柱子上方能装多少水，最后将所有柱子的积水量累加起来。这种处理方式类似微积分中对局部结果进行累加。

对于柱子 i，它能接的水量由自身高度、左侧最高柱子的高度和右侧最高柱子的高度共同决定，计算公式为：

$$
water[i] = \min(left_max, right_max) - height[i]
$$

这和盛最多水的容器中受到较短一侧限制的思想类似。

暴力解法 $O(n^2)$

对于每个柱子 i，完整扫描它左侧和右侧的柱子，分别得到左侧最高高度和右侧最高高度，再根据公式计算当前柱子的积水量。

每个柱子都需要进行左右扫描，因此时间复杂度为 $O(n^2)$，空间复杂度为 $O(1)$。

前后缀最大值 $O(n)$

如果想优化时间复杂度，可以用空间换时间，维护两个数组 left_max[] 和 right_max[]：

  • left_max[i] 记录柱子 i 左侧（包含自身）出现过的最高柱子高度。
  • right_max[i] 记录柱子 i 右侧（包含自身）出现过的最高柱子高度。

这样就可以在 $O(1)$ 时间内得到每个柱子两侧的最高高度。遍历一次数组计算积水量，时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

左右指针 $O(n)$

最终可以进一步优化空间复杂度：利用左右指针将 left_max[] 和 right_max[] 两个数组简化为两个变量 left_max 和 right_max。

两个变量分别记录从左右两侧扫描到当前位置时见过的最高柱子高度。每轮比较左右两侧当前柱子的高度，处理较矮的一侧，并移动对应指针：

  • 如果左侧柱子更矮，左侧当前能接多少水由 left_max 和右侧最高高度共同限制。由于右侧当前柱子更高，右侧至少提供了一个不低于当前左侧柱子的边界，因此可以计算左侧积水量并移动左指针。
  • 如果右侧柱子更矮，则对称地计算右侧积水量并移动右指针。

也就是说，较矮的一侧的积水上限已经可以确定，所以每次只处理较矮的一侧。这样只需要遍历数组一次，时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        left_max, right_max = -1, -1
        water = 0

        while left < right:
            left_max = max(left_max, height[left])
            right_max = max(right_max, height[right])

            if height[left] < height[right]:
                water += min(left_max, right_max) - height[left]
                left += 1
            else:
                water += min(left_max, right_max) - height[right]
                right -= 1

        return water
 评论
评论插件加载失败
正在加载评论插件
  1. 1. 基本思路
  2. 2. 题目索引
  3. 3. 题目记录
    1. 3.1. 移动零
      1. 3.1.1. 题目描述
      2. 3.1.2. 示例
      3. 3.1.3. 提示
      4. 3.1.4. 思路
      5. 3.1.5. 原始思路 $O(n^2)$
      6. 3.1.6. 优化思路 $O(n)$
      7. 3.1.7. 优化解法
    2. 3.2. 盛最多水的容器
      1. 3.2.1. 题目描述
      2. 3.2.2. 示例
      3. 3.2.3. 提示
      4. 3.2.4. 思路 $O(n)$
      5. 3.2.5. 解答
    3. 3.3. 三数之和
      1. 3.3.1. 题目描述
      2. 3.3.2. 示例
      3. 3.3.3. 提示
      4. 3.3.4. 思路 $O(n^2)$
      5. 3.3.5. 集合与元组去重 $O(n^2)$
      6. 3.3.6. 双指针去重 $O(n^2)$
    4. 3.4. 接雨水
      1. 3.4.1. 题目描述
      2. 3.4.2. 示例
      3. 3.4.3. 提示
      4. 3.4.4. 思路
      5. 3.4.5. 暴力解法 $O(n^2)$
      6. 3.4.6. 前后缀最大值 $O(n)$
      7. 3.4.7. 左右指针 $O(n)$
      8. 3.4.8. 解法
  1. 1. 基本思路
  2. 2. 题目索引
  3. 3. 题目记录
    1. 3.1. 移动零
      1. 3.1.1. 题目描述
      2. 3.1.2. 示例
      3. 3.1.3. 提示
      4. 3.1.4. 思路
      5. 3.1.5. 原始思路 $O(n^2)$
      6. 3.1.6. 优化思路 $O(n)$
      7. 3.1.7. 优化解法
    2. 3.2. 盛最多水的容器
      1. 3.2.1. 题目描述
      2. 3.2.2. 示例
      3. 3.2.3. 提示
      4. 3.2.4. 思路 $O(n)$
      5. 3.2.5. 解答
    3. 3.3. 三数之和
      1. 3.3.1. 题目描述
      2. 3.3.2. 示例
      3. 3.3.3. 提示
      4. 3.3.4. 思路 $O(n^2)$
      5. 3.3.5. 集合与元组去重 $O(n^2)$
      6. 3.3.6. 双指针去重 $O(n^2)$
    4. 3.4. 接雨水
      1. 3.4.1. 题目描述
      2. 3.4.2. 示例
      3. 3.4.3. 提示
      4. 3.4.4. 思路
      5. 3.4.5. 暴力解法 $O(n^2)$
      6. 3.4.6. 前后缀最大值 $O(n)$
      7. 3.4.7. 左右指针 $O(n)$
      8. 3.4.8. 解法