Python详解双指针技巧

紫丁香

392人浏览 · 2026-03-06 23:37:07

紫丁香 · 2026-03-06 23:37:07 发布

双指针技巧是一种使用两个指针同时遍历数据结构的算法技巧。双指针可以大大简化某些问题的解决，提高算法效率。

1.核心技巧总结

技巧	适用场景	时间复杂度
快慢指针	链表问题	O(n)
左右指针	数组问题	O(n)
滑动窗口	子数组/子串问题	O(n)
对撞指针	有序数组	O(n)
分离指针	双数组问题	O(n)

2.题目详解

2.1 盛最多水的容器

给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明：你不能倾斜容器。

输入：height = [1,8,6,2,5,4,8,3,7]
输出：49

2.1.1 问题分析

这道题可以使用对撞指针解决。关键点在于：每次移动较矮的那个指针，因为移动较高的指针只会减少宽度，而高度不会增加。

2.1.2 解题思路

使用左右双指针，分别指向数组的两端
计算当前容器的面积
移动较矮的那个指针
重复直到两个指针相遇

2.1.3 代码实现

from typing import List

def max_area(height: List[int]) -> int:
    left, right = 0, len(height) - 1
    max_water = 0

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

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

    return max_water


if __name__ == "__main__":
    # 测试用例1
    height1 = [1, 8, 6, 2, 5, 4, 8, 3, 7]
    print(f"输入: height = {height1}")
    print(f"输出: {max_area(height1)}")
    print()

    # 测试用例2
    height2 = [1, 1]
    print(f"输入: height = {height2}")
    print(f"输出: {max_area(height2)}")
    print()

    # 测试用例3
    height3 = [4, 3, 2, 1, 4]
    print(f"输入: height = {height3}")
    print(f"输出: {max_area(height3)}")

2.2 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c，使得 a + b + c = 0？请你找出所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]


输入：nums = []
输出：[]


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

2.2.1 问题分析

这道题可以使用对撞指针解决。先排序，然后固定一个数，使用双指针找另外两个数。

2.2.2 解题思路

先对数组排序
固定第一个数，使用双指针找另外两个数
跳过重复的元素，避免重复解

2.2.3 代码实现

def three_sum(nums):
    if len(nums) < 3:
        return []
    nums.sort()
    n = len(nums)
    res = []
    for i in range(n -2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i+1, n-1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                res.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]:
                    left += 1
                while left < right and nums[right] == nums[right-1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return res

# 测试代码
if __name__ == "__main__":
    # 测试用例1
    nums1 = [-1, 0, 1, 2, -1, -4]
    print(f"输入: nums = {nums1}")
    print(f"输出: {three_sum(nums1)}")
    print()

    # 测试用例2
    nums2 = []
    print(f"输入: nums = {nums2}")
    print(f"输出: {three_sum(nums2)}")
    print()

    # 测试用例3
    nums3 = [0]
    print(f"输入: nums = {nums3}")
    print(f"输出: {three_sum(nums3)}")

2.3 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

输入：nums = [-1,2,1,-4], target = 1
输出：2


输入：nums = [0,0,0], target = 1
输出：0


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

2.3.1 问题分析

这道题可以使用对撞指针解决。先排序，然后固定一个数，使用双指针找另外两个数。

2.3.2 解题思路

先对数组排序
固定第一个数，使用双指针找另外两个数
计算当前和与目标值的差距
更新最接近的和

2.3.3 代码实现

def three_sum_closest(nums, target):
    nums.sort()
    n = len(nums)
    closest_sum = float('inf')
    for i in range(n -2):
        left, right = i+1, n-1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum

            if current_sum < target:
                left += 1
            elif current_sum > target:
                right -= 1
            else:
                return current_sum

    return closest_sum

# 测试代码
if __name__ == "__main__":
    # 测试用例1
    nums1 = [-1, 2, 1, -4]
    target1 = 1
    print(f"输入: nums = {nums1}, target = {target1}")
    print(f"输出: {three_sum_closest(nums1, target1)}")
    print()

    # 测试用例2
    nums2 = [0, 0, 0]
    target2 = 1
    print(f"输入: nums = {nums2}, target = {target2}")
    print(f"输出: {three_sum_closest(nums2, target2)}")
    print()

    # 测试用例3
    nums3 = [0, 2, 1, -3]
    target3 = 0
    print(f"输入: nums = {nums3}, target = {target3}")
    print(f"输出: {three_sum_closest(nums3, target3)}")

2.4 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。注意：答案中不可以包含重复的四元组。

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

输入：nums = [], target = 0
输出：[]

2.4.1 问题分析

这道题可以使用对撞指针解决。先排序，然后固定两个数，使用双指针找另外两个数。

2.4.2 解题思路

先对数组排序
固定两个数，使用双指针找另外两个数
跳过重复的元素，避免重复解

2.4.3 代码实现

from typing import List


def four_sum(nums: List[int], target: int) -> List[List[int]]:
    """
    四数之和

    Args:
        nums: 整数数组
        target: 目标值

    Returns:
        所有不重复的四元组
    """
    result = []
    nums.sort()
    n = len(nums)

    for i in range(n - 3):
        # 跳过重复元素
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        for j in range(i + 1, n - 2):
            # 跳过重复元素
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue

            # 使用双指针
            left, right = j + 1, n - 1

            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]

                if total == target:
                    result.append([nums[i], nums[j], nums[left], nums[right]])

                    # 跳过重复元素
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    left += 1
                    right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1

    return result


# 测试代码
if __name__ == "__main__":
    # 测试用例1
    nums1 = [1, 0, -1, 0, -2, 2]
    target1 = 0
    print(f"输入: nums = {nums1}, target = {target1}")
    print(f"输出: {four_sum(nums1, target1)}")
    print()

    # 测试用例2
    nums2 = [2, 2, 2, 2, 2]
    target2 = 8
    print(f"输入: nums = {nums2}, target = {target2}")
    print(f"输出: {four_sum(nums2, target2)}")
    print()

    # 测试用例3
    nums3 = []
    target3 = 0
    print(f"输入: nums = {nums3}, target = {target3}")
    print(f"输出: {four_sum(nums3, target3)}")

2.5 两数之和 II

给定一个已按照非递减顺序排列的整数数组 numbers，请你从数组中找出两个数满足相加之和等于目标数 target。函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标从 1 开始计数，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]

输入：numbers = [2,3,4], target = 6
输出：[1,3]

输入：numbers = [-1,0], target = -1
输出：[1,2]

2.5.1 问题分析

这道题可以使用对撞指针解决。由于数组已排序，可以从两端向中间遍历。

2.5.2 解题思路

使用左右双指针
如果和小于目标值，移动左指针
如果和大于目标值，移动右指针
如果和等于目标值，返回结果

2.5.3 代码实现

from typing import List


def two_sum(numbers: List[int], target: int) -> List[int]:
    """
    两数之和 II

    Args:
        numbers: 已排序的整数数组
        target: 目标值

    Returns:
        两个数的下标（从1开始）
    """
    left, right = 0, len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]

        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return []


if __name__ == "__main__":
    numbers1 = [2, 7, 11, 15]
    target1 = 9
    print(f"输入: numbers = {numbers1}, target = {target1}")
    print(f"输出: {two_sum(numbers1, target1)}")
    print()

    numbers2 = [2, 3, 4]
    target2 = 6
    print(f"输入: numbers = {numbers2}, target = {target2}")
    print(f"输出: {two_sum(numbers2, target2)}")
    print()

    numbers3 = [-1, 0]
    target3 = -1
    print(f"输入: numbers = {numbers3}, target = {target3}")
    print(f"输出: {two_sum(numbers3, target3)}")

2.6 删除有序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

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

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

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

2.6.1 问题分析

这道题可以使用双指针解决。一个指针指向当前不重复的元素，另一个指针遍历数组。

2.6.2 解题思路

使用双指针
一个指针指向当前不重复的元素
另一个指针遍历数组
如果元素不重复，更新不重复指针
返回不重复指针的位置

2.6.3 代码实现

from typing import List


def remove_duplicates(nums: List[int]) -> int:
    """
    删除有序数组中的重复项

    Args:
        nums: 已排序的整数数组

    Returns:
        移除重复项后的新长度
    """
    if not nums:
        return 0

    slow = 0

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

    return slow + 1


# 测试代码
if __name__ == "__main__":
    # 测试用例1
    nums1 = [1, 1, 2]
    print(f"输入: nums = {nums1}")
    print(f"输出: {remove_duplicates(nums1)}")
    print()

    # 测试用例2
    nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
    print(f"输入: nums = {nums2}")
    print(f"输出: {remove_duplicates(nums2)}")
    print()

    # 测试用例3
    nums3 = [1, 2, 3]
    print(f"输入: nums = {nums3}")
    print(f"输出: {remove_duplicates(nums3)}")

2.7 删除有序数组中的重复项 II

给你一个有序数组 nums，请你原地删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

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

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

2.7.1 问题分析

这道题可以使用双指针解决。一个指针指向当前有效元素的位置，另一个指针遍历数组。

2.7.2 解题思路

1.使用双指针

2.检查当前元素是否与前两个元素相同

3.如果不相同，更新有效指针

2.7.3 代码实现

from typing import List


def remove_duplicates(nums: List[int]) -> int:
    """
    删除有序数组中的重复项 II

    Args:
        nums: 已排序的整数数组

    Returns:
        删除后数组的新长度
    """
    if len(nums) <= 2:
        return len(nums)

    slow = 2

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

    return slow


if __name__ == "__main__":
    nums1 = [1, 1, 1, 2, 2, 3]
    print(f"输入: nums = {nums1}")
    print(f"输出: {remove_duplicates(nums1)}")
    print()

    nums2 = [0, 0, 1, 1, 1, 1, 2, 3, 3]
    print(f"输入: nums = {nums2}")
    print(f"输出: {remove_duplicates(nums2)}")

2.8 颜色分类

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。

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

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

2.8.1 问题分析

这道题可以使用三指针解决。使用三个指针分别指向0的末尾、当前元素和2的开头。

2.8.2 解题思路

1.使用三个指针

2.遇到0交换到前面

3.遇到2交换到后面

4.遇到1跳过

2.8.3 代码实现

from typing import List


def sort_colors(nums: List[int]) -> None:
    """
    颜色分类

    Args:
        nums: 整数数组
    """
    left, current, right = 0, 0, len(nums) - 1

    while current <= right:
        if nums[current] == 0:
            nums[left], nums[current] = nums[current], nums[left]
            left += 1
            current += 1
        elif nums[current] == 2:
            nums[current], nums[right] = nums[right], nums[current]
            right -= 1
        else:
            current += 1


if __name__ == "__main__":
    nums1 = [2, 0, 2, 1, 1, 0]
    print(f"输入: nums = {nums1}")
    sort_colors(nums1)
    print(f"输出: {nums1}")
    print()

    nums2 = [2, 0, 1]
    print(f"输入: nums = {nums2}")
    sort_colors(nums2)
    print(f"输出: {nums2}")

2.9 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回 0。

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2

输入：target = 4, nums = [1,4,4]
输出：1

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

2.9.1 问题分析

这道题可以使用滑动窗口解决。使用双指针维护一个窗口，窗口内的和大于等于 target。

2.9.2 解题思路

1.使用滑动窗口

2.扩展右边界，增加和

3.当和大于等于 target 时，收缩左边界

4.记录最小长度

2.9.3 代码实现

from typing import List


def min_sub_array_len(target: int, nums: List[int]) -> int:
    """
    长度最小的子数组

    Args:
        target: 目标值
        nums: 整数数组

    Returns:
        最小长度
    """
    left = 0
    current_sum = 0
    min_length = float('inf')

    for right in range(len(nums)):
        current_sum += nums[right]

        while current_sum >= target:
            min_length = min(min_length, right - left + 1)
            current_sum -= nums[left]
            left += 1

    return min_length if min_length != float('inf') else 0


if __name__ == "__main__":
    target1 = 7
    nums1 = [2, 3, 1, 2, 4, 3]
    print(f"输入: target = {target1}, nums = {nums1}")
    print(f"输出: {min_sub_array_len(target1, nums1)}")
    print()

    target2 = 4
    nums2 = [1, 4, 4]
    print(f"输入: target = {target2}, nums = {nums2}")
    print(f"输出: {min_sub_array_len(target2, nums2)}")
    print()

    target3 = 11
    nums3 = [1, 1, 1, 1, 1, 1, 1, 1]
    print(f"输入: target = {target3}, nums = {nums3}")
    print(f"输出: {min_sub_array_len(target3, nums3)}")

2.10 水果成篮

在一排树中，第 i 棵树产生 tree[i] 型的水果。你可以从你选定的任何树开始，然后重复执行以下步骤：把你这棵树上的水果放进你的篮子里。如果你做不到，就停下来。移动到当前树右侧的下一棵树。请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至你停止。你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。用这个程序你能收集的水果的最大数量是多少？

输入：fruits = [1,2,1]
输出：3

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

输入：fruits = [1,2,3,2,2]
输出：4

2.10.1 问题分析

这道题可以使用滑动窗口解决。维护一个窗口，窗口内最多有两种类型的水果。

2.10.2 解题思路

1.使用滑动窗口

2.使用哈希表记录水果类型和数量

3.当类型超过2时，收缩左边界

4.记录最大长度

2.10.3 代码实现

from typing import List
from collections import defaultdict


def total_fruit(fruits: List[int]) -> int:
    """
    水果成篮

    Args:
        fruits: 水果类型数组

    Returns:
        最大水果数量
    """
    left = 0
    fruit_count = defaultdict(int)
    max_fruits = 0

    for right in range(len(fruits)):
        fruit_count[fruits[right]] += 1

        while len(fruit_count) > 2:
            fruit_count[fruits[left]] -= 1
            if fruit_count[fruits[left]] == 0:
                del fruit_count[fruits[left]]
            left += 1

        max_fruits = max(max_fruits, right - left + 1)

    return max_fruits


if __name__ == "__main__":
    fruits1 = [1, 2, 1]
    print(f"输入: fruits = {fruits1}")
    print(f"输出: {total_fruit(fruits1)}")
    print()

    fruits2 = [0, 1, 2, 2]
    print(f"输入: fruits = {fruits2}")
    print(f"输出: {total_fruit(fruits2)}")
    print()

    fruits3 = [1, 2, 3, 2, 2]
    print(f"输入: fruits = {fruits3}")
    print(f"输出: {total_fruit(fruits3)}")

2.11 接雨水

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

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

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

输入：height = [0,0,0,0]
输出：0

2.11.1 问题分析

这道题可以使用双指针解决。从两端向中间遍历，计算每个位置能接的雨水。

2.11.2 解题思路

1.使用双指针，分别指向数组的两端

2.计算左右两边的最大高度

3.计算当前位置能接的雨水

4.移动较矮的那个指针

5.返回总雨水量

2.11.3 代码实现

from typing import List


def trap(height: List[int]) -> int:
    """
    接雨水

    Args:
        height: 柱子高度数组

    Returns:
        能接多少雨水
    """
    if not height:
        return 0

    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0

    while left < right:
        # 计算当前位置能接的雨水
        water += max(min(left_max, right_max) - height[left], min(left_max, right_max) - height[right])

        # 更新左右两边的最大高度
        left_max = max(left_max, height[left])
        right_max = max(right_max, height[right])

        # 移动较矮的那个指针
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return water


# 测试代码
if __name__ == "__main__":
    # 测试用例1
    height1 = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
    print(f"输入: height = {height1}")
    print(f"输出: {trap(height1)}")
    print()

    # 测试用例2
    height2 = [4, 2, 0, 3, 2, 5]
    print(f"输入: height = {height2}")
    print(f"输出: {trap(height2)}")
    print()

    # 测试用例3
    height3 = [0, 0, 0, 0]
    print(f"输入: height = {height3}")
    print(f"输出: {trap(height3)}")

2.12 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为：k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k，例如不会出现像 3a 或 2[4] 的输入。

输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "3[a2[c]]"
输出："accaccacc"

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

2.12.1 问题分析

这道题可以使用栈解决。遇到数字时记录重复次数，遇到 '[' 时压栈，遇到 ']' 时弹出并构建字符串。

2.12.2 解题思路

1.使用两个栈，一个存储数字，一个存储字符串

2.遇到数字时解析完整数字

3.遇到 '[' 时压栈当前状态

4.遇到 ']' 时弹出并构建字符串

2.12.3 代码实现

def decode_string(s: str) -> str:
    """
    字符串解码

    Args:
        s: 编码字符串

    Returns:
        解码后的字符串
    """
    num_stack = []
    str_stack = []
    current_num = 0
    current_str = ""

    for char in s:
        if char.isdigit():
            current_num = current_num * 10 + int(char)
        elif char == '[':
            num_stack.append(current_num)
            str_stack.append(current_str)
            current_num = 0
            current_str = ""
        elif char == ']':
            repeat_times = num_stack.pop()
            prev_str = str_stack.pop()
            current_str = prev_str + current_str * repeat_times
        else:
            current_str += char

    return current_str


if __name__ == "__main__":
    s1 = "3[a]2[bc]"
    print(f"输入: s = '{s1}'")
    print(f"输出: '{decode_string(s1)}'")
    print()

    s2 = "3[a2[c]]"
    print(f"输入: s = '{s2}'")
    print(f"输出: '{decode_string(s2)}'")
    print()

    s3 = "2[abc]3[cd]ef"
    print(f"输入: s = '{s3}'")
    print(f"输出: '{decode_string(s3)}'")