核心：有序数组 + 相向双指针，将暴力 O(n²)、O(n³) 复杂度优化到更高效的级别，是解决数组求和、计数、最接近值、三角形判定等问题的核心思路。
一、经典题目（讲解）
1. 盛最多水的容器（LeetCode 经典题）
题目描述
给定一个长度为 n 的整数数组 height，有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
核心思路
- 容器容量 = 两线间距 × 两线中较短的高度
- 相向双指针：左指针L=0，右指针R=n-1，短边指针向内移动
- 移动短边才有可能找到更大容量，移动长边无意义（间距缩小，高度不变 / 变小，容量必减小）
复杂度
时间：O(n)（仅遍历一次数组，双指针移动总次数为 n）
空间：O(1)（仅用常数变量，无额外数组）
Python 实现
def maxArea(height):
# 初始化左指针在数组起始位置
left = 0
# 初始化右指针在数组末尾
right = len(height) - 1
# 记录最大盛水量
max_water = 0
# 当左右指针没有相遇时循环
while left < right:
# 计算当前容器宽度：右指针下标 - 左指针下标
width = right - left
# 容器高度取左右两边较小值
h = min(height[left], height[right])
# 计算当前盛水量
current_water = width * h
# 更新最大盛水量
max_water = max(max_water, current_water)
# 移动较短的边，才有可能获得更大容量
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_water2. 接雨水（LeetCode 经典题）
题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
核心思路
每个位置能接的雨水量 = min(左侧最大高度，右侧最大高度) - 当前高度
两种解法核心一致，均围绕“左右最大高度”计算，差异在于空间复杂度：
解法 1（前缀 / 后缀数组）：用额外数组存储左右最大高度，直观易理解
解法 2（双指针优化）：用变量动态维护左右最大高度，无需额外数组，空间最优
解法 1：前缀 / 后缀最大值数组
预处理前缀最大值数组：记录每个位置左侧（含自身）的最高柱子高度
预处理后缀最大值数组：记录每个位置右侧（含自身）的最高柱子高度
遍历每个位置，按核心公式累加接水量
复杂度
时间：O(n)（3 次遍历数组，分别处理前缀、后缀数组和计算结果）
空间：O(n)（额外两个大小为 n 的数组）
Python 实现
def trap(height):
n = len(height)
if n == 0:
return 0
# 前缀最大值数组：pre_max[i]表示i位置左侧（含i）最高柱子
pre_max = [0] * n
pre_max[0] = height[0]
for i in range(1, n):
pre_max[i] = max(pre_max[i-1], height[i])
# 后缀最大值数组：suf_max[i]表示i位置右侧（含i）最高柱子
suf_max = [0] * n
suf_max[-1] = height[-1]
for i in range(n-2, -1, -1):
suf_max[i] = max(suf_max[i+1], height[i])
# 累加总接水量
res = 0
for i in range(n):
# 当前位置能接的水 = 左右最小高度 - 当前高度
res += min(pre_max[i], suf_max[i]) - height[i]
return res解法 2：双指针优化（空间 O(1)）
用单个变量维护左侧最大高度（pre_max）和右侧最大高度（suf_max），无需额外数组
相向双指针：左指针从 0 开始，右指针从末尾开始，逐步向中间靠拢
哪边最大高度更小，计算哪边的接水量，移动对应指针，动态更新最大高度
复杂度
时间：O(n)（仅遍历一次数组，双指针移动总次数为 n）
空间：O(1)（仅用常数变量，无额外数组）
Python 实现
def trap(height):
n = len(height)
if n == 0:
return 0
left = 0 # 左指针
right = n - 1 # 右指针
pre_max = 0 # 左侧遍历过的最大高度
suf_max = 0 # 右侧遍历过的最大高度
res = 0 # 总接水量
# 左右指针未相遇时循环
while left <= right:
# 更新左侧最大高度
pre_max = max(pre_max, height[left])
# 更新右侧最大高度
suf_max = max(suf_max, height[right])
# 左侧最大高度更小，计算左指针位置接水量
if pre_max < suf_max:
res += pre_max - height[left]
left += 1
# 右侧最大高度更小，计算右指针位置接水量
else:
res += suf_max - height[right]
right -= 1
return res二、双指针专项练习
验证回文串：核心考察“相向双指针跳过无效字符”的应用
给植物浇水 II：核心考察“相向双指针分区域处理”，结合条件判断优化流程
1. 125. 验证回文串（LeetCode）
题目描述
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
示例
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。
Python 代码
class Solution:
def isPalindrome(self, s: str) -> bool:
# 初始化左右双指针，分别指向字符串首尾
i, j = 0, len(s) - 1
# 当左指针小于右指针时，持续判断
while i < j:
# 左指针指向非字母数字字符，右移跳过
if not s[i].isalnum():
i += 1
# 右指针指向非字母数字字符，左移跳过
elif not s[j].isalnum():
j -= 1
# 左右指针均为字母数字，转换为小写后判断是否相等
elif s[i].lower() == s[j].lower():
# 相等则继续向中间靠拢
i += 1
j -= 1
# 不相等则直接返回false，不是回文串
else:
return False
# 循环结束，所有对应位置均匹配，返回true
return True2. 2105. 给植物浇水 II（LeetCode）
题目描述
Alice 和 Bob 打算给花园里的 n 株植物浇水。植物排成一行，从左到右进行标记，编号从 0 到 n - 1 。其中，第 i 株植物的位置是 x = i 。
每一株植物都需要浇特定量的水。Alice 和 Bob 每人有一个水罐，最初是满的 。他们按下面描述的方式完成浇水：
Alice 按 从左到右 的顺序给植物浇水，从植物 0 开始。Bob 按 从右到左 的顺序给植物浇水，从植物 n - 1 开始。他们 同时 给植物浇水。
无论需要多少水，为每株植物浇水所需的时间都是相同的。
如果 Alice/Bob 水罐中的水足以 完全 灌溉植物，他们 必须 给植物浇水。否则，他们 首先（立即）重新装满罐子，然后给植物浇水。
如果 Alice 和 Bob 到达同一株植物，那么当前水罐中水 更多 的人会给这株植物浇水。如果他俩水量相同，那么 Alice 会给这株植物浇水。
给你一个下标从 0 开始的整数数组 plants ，数组由 n 个整数组成。其中，plants[i] 为第 i 株植物需要的水量。另有两个整数 capacityA 和 capacityB 分别表示 Alice 和 Bob 水罐的容量。返回两人浇灌所有植物过程中重新灌满水罐的 次数 。
示例
输入：plants = [2,2,3,3], capacityA = 5, capacityB = 5
输出：1
解释：
最初，Alice 和 Bob 的水罐中各有 5 单元水。
Alice 给植物 0 浇水，Bob 给植物 3 浇水。
Alice 和 Bob 现在分别剩下 3 单元和 2 单元水。
Alice 有足够的水给植物 1 ，所以她直接浇水。Bob 的水不够给植物 2 ，所以他先重新装满水，再浇水。
所以，两人浇灌所有植物过程中重新灌满水罐的次数 = 0 + 0 + 1 + 0 = 1 。
Python 代码
from typing import List
class Solution:
def minimumRefill(self, plants: List[int], capacityA: int, capacityB: int) -> int:
# 记录重新灌水的总次数
ans = 0
# 植物的总数量
n = len(plants)
# 初始化左右双指针，Alice从左（0）开始，Bob从右（n-1）开始
l, r = 0, n-1
# 初始化Alice和Bob水罐当前的水量（初始为满罐）
wata, watb = capacityA, capacityB
# 当左指针小于等于右指针时，持续浇水（覆盖所有植物）
while l <= r:
# 情况1：左右指针相遇，即两人到达同一株植物
if l == r:
# 判断两人水罐中最大水量是否能浇完当前植物，不够则需重新灌水1次
if max(wata, watb) < plants[l]:
ans += 1
# 同一株植物只需浇一次，直接退出循环
break
# 情况2：Alice浇水（左指针位置）
# 若当前水量不足，重新灌满，次数+1，更新水量为满罐
if wata < plants[l]:
ans += 1
wata = capacityA
# 浇完当前植物，减去对应水量
wata -= plants[l]
# 情况3：Bob浇水（右指针位置）
# 若当前水量不足，重新灌满，次数+1，更新水量为满罐
if watb < plants[r]:
ans += 1
watb = capacityB
# 浇完当前植物，减去对应水量
watb -= plants[r]
# 两人同时向中间移动指针
l += 1
r -= 1
# 返回总重新灌水次数
return ans