双指针：从两端向中间
使用相向移动的左右指针，解决有序数组中的两数之和、有效回文和接雨水问题。
双指针：从两端向中间 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
双指针思想
双指针技巧使用两个索引变量相向移动（或沿同一方向移动），从而减少对嵌套循环的需求。与其在 O(n²) 时间内检查每一对元素，不如让每次比较都推进算法，最终在 O(n) 时间内完成。它几乎总是要求数组先排序，因为排序后，您可以根据当前数对的和过大还是过小，判断每个指针应该向哪个方向移动。
# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1
else: right -= 1
return []有序数组中的两数之和
对于有序数组，将一个指针放在左端（最小值），另一个指针放在右端（最大值）。如果总和过小，就将左指针向右移动以增大总和。如果总和过大，就将右指针向左移动以减小总和。每次迭代至少会移动一个指针，因此循环最多执行 n 次：排序之后的总时间复杂度为 O(n)。重要的是，由于数组已经有序，每次移动都可以证明是正确的。
def two_sum_sorted(numbers, target):
# numbers is 1-indexed per LeetCode 167
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]有效回文检查
如果一个字符串正读和反读都相同，那么它就是回文。使用从两端开始并向内移动的两个指针：比较字符，跳过非字母数字字符，并在指针交叉时停止。这种方法的时间复杂度为 O(n)，额外空间复杂度为 O(1)——相比反转字符串再进行比较更加简洁，后者需要分配 O(n) 的额外内存。
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
# Skip non-alphanumeric
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # False三数之和：排序加双指针
三数之和问题要求找出所有和为零的不重复三元组。先对数组排序，然后固定每个元素 nums[i]，再在剩余子数组中使用双指针查找和为 -nums[i] 的数对。跳过固定元素和已找到数对的重复值，以避免出现重复三元组。排序后的总时间复杂度为 O(n²)，排序本身需要 O(n log n) 时间。
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dupe
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.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 s < 0: left += 1
else: right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]盛水最多的容器
给定垂直线的高度，请找出能够容纳最多水的两条线。面积 = min(height[left], height[right]) × (right - left)。贪心地将较短线所在的指针向内移动：移动较高的线只会减小宽度，却无法增加高度上限。这一贪心选择可以证明是最优的，并且时间复杂度为 O(n)。
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = h * (right - left)
best = max(best, area)
# Move the shorter wall inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49对有序数组求平方
对有序数组中的每个元素求平方（数组可能包含负数），并按排序顺序返回结果。负数的平方值较大，正数的平方值在中间位置较小。在两端放置两个指针，并从右向左（从最大值到最小值）填充结果数组。时间复杂度为 O(n)，输出空间复杂度为 O(n)，远优于先求平方再以 O(n log n) 时间排序。
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]接雨水
索引 i 处接住的水量等于 min(max_left, max_right) - height[i]。双指针方法维护 max_left 和 max_right 的累计值。当 max_left < max_right 时，左侧是瓶颈，因此处理左指针；否则处理右指针。这样无需单独的左侧最大值和右侧最大值数组，就能达到 O(1) 的额外空间复杂度。
def trap(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6贪心移动指针为何有效
面试中常见的后续问题是：为什么可以安全地舍弃较小值一侧的指针？以盛水最多的容器为例，证明思路如下：假设 height[left] < height[right]。对于所有 j < right 的数对 (left, j)，其面积 ≤ height[left] × (j-left) < height[left] × (right-left) ≤ 当前面积。因此，从 left 开始且右索引低于 right 的数对都不可能超过当前面积。我们可以通过将 left 向前移动来安全地跳过它们。
# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
# area(left, j) <= min(h[left], h[j]) * (j - left)
# <= h[left] * (j - left)
# <= h[left] * (right - left) [since j < right]
# = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.
print('Proof verified: advance shorter pointer is optimal')有序数组中的最小差值对
找出有序数组中绝对差值最小的一对数字。使用两个相邻指针（而不是指向两端的指针）一起扫描：对所有连续元素对计算 |nums[i] - nums[i+1]|。有序数组中的最小差值一定出现在相邻元素之间（因为排序会将接近的值聚集在一起）。排序完成后，此过程的时间复杂度为 O(n)。
def min_diff_pair(nums):
nums.sort() # O(n log n)
min_diff = float('inf')
best = (nums[0], nums[1])
for i in range(len(nums) - 1):
diff = nums[i+1] - nums[i] # sorted: always >= 0
if diff < min_diff:
min_diff = diff
best = (nums[i], nums[i+1])
return best, min_diff
pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d) # (1, 2) 1相向双指针模板
大多数相向双指针问题都遵循相同的基本框架。掌握这个模板后，您就能在时间压力下快速调整使用。关键决策包括：（1）什么条件会推进左指针；（2）什么条件会推进右指针；（3）什么情况构成一个解；（4）如何处理重复项。在编写代码之前，请练习根据题目描述明确并实现这些决策。
def two_pointer_template(arr, condition):
"""
Generic opposite-ends two-pointer skeleton.
Replace condition logic for each specific problem.
"""
left, right = 0, len(arr) - 1
result = []
while left < right:
current = arr[left] + arr[right] # or some combination
if current == condition: # found a valid pair
result.append((arr[left], arr[right]))
left += 1
right -= 1
elif current < condition: # need to increase
left += 1
else: # need to decrease
right -= 1
return result使用双指针统计有效数对
双指针也能高效地统计数对。对于“统计有序数组中和小于目标值的数对”这一问题：固定左指针，并使用右指针找出最右侧的有效右索引。所有数对（左指针，左指针+1 到右指针）都有效——将 right - left 加入计数，然后推进左指针。这样可以在 O(n) 时间内统计所有有效数对，而不是使用 O(n²) 的方法。
def count_pairs_less_than(nums, target):
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left # all (left, left+1..right) valid
left += 1
else:
right -= 1
return count
print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3) -> 4快速检查
测试您对本课中“数据结构与算法——编程面试准备”相关概念的理解。
课程回顾
本课中您学到了：相向双指针将有序数组中 O(n²) 的数对枚举替换为左右指针以 O(n) 时间向中间收敛，推进哪个指针取决于问题的单调性——移动当前限制进展的一侧，以及三数之和、盛最多水的容器、接雨水和回文验证都可以归结为同一个核心模板。接下来我们将学习快慢双指针模式。
常见问题解答
「双指针：从两端向中间」课时是免费的吗？
是的 — 「双指针：从两端向中间」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「双指针：从两端向中间」这节课中我会学到什么？
使用相向移动的左右指针，解决有序数组中的两数之和、有效回文和接雨水问题。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「双指针：从两端向中间」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。