双指针经典算法题实战解析
双指针是处理数组和链表问题的高效技巧，核心在于利用两个指针的相对运动来减少时间复杂度。下面结合几道经典题目，聊聊其中的设计思路与边界细节。
1. 移动零 (Move Zeroes)
题目链接： LeetCode 283
这道题的目标是将数组中的 0 移动到末尾，同时保持非零元素的相对顺序。最直观的思路是用双指针将数组划分为三个区间：已处理的非零区、待处理的零区、未处理区。
我们可以维护一个 dest 指针指向非零区的末尾，初始为 -1；cur 指针遍历数组。当 cur 遇到非零元素时，先扩展非零区（++dest），再交换 dest 和 cur 的值。如果 cur 遇到 0，则直接跳过，让它留在零区。
def moveZeroes(nums):
dest = -1
for cur in range(len(nums)):
if nums[cur] != 0:
dest += 1
nums[dest], nums[cur] = nums[cur], nums[dest]
注意，循环结束时 cur 会遍历完整个数组，此时所有非零元素都已按序前移，剩余位置自然填充为 0。
2. 复写零 (Duplicate Zeros)
题目链接： LeetCode 1089
如果直接从前往后模拟复写 0，后面的数据会被覆盖。因此，更稳妥的策略是从后往前操作。
我们需要先确定最后一个需要复写的数字位置。可以设 cur 从头开始，dest 从逻辑上的末尾开始（考虑复写后的长度）。当 cur 遇到 0 时，dest 走两步并标记为 0；遇到非 0 时，dest 走一步复制值。
这里有个关键点：dest 可能会走到原数组范围之外，这通常意味着最后一个 0 被截断了，需要单独处理边界情况。实际编码时，建议先计算有效长度，再倒序填充。
3. 快乐数 (Happy Number)
题目链接： LeetCode 202
判断一个数是否为快乐数，本质上是检测数字变换过程中是否存在环。无论结果是 1 还是进入死循环，最终都会形成闭环。
使用快慢指针法：定义一个函数计算数字各位平方和。快指针每次运算两次，慢指针每次运算一次。如果存在环，两者必会相遇。相遇时若值为 1，则是快乐数；否则不是。
def get_next(n):
total_sum = 0
while n > 0:
n, digit = divmod(n, 10)
total_sum += digit ** 2
return total_sum
def isHappy(n):
slow = n
fast = get_next(n)
while fast != 1 and slow != fast:
slow = get_next(slow)
fast = get_next(get_next(fast))
return fast == 1
注意初始化时不要让两指针相等，否则无法进入循环检测。
4. 盛最多水的容器 (Container With Most Water)
题目链接： LeetCode 11
暴力枚举需要 O(N²)，利用单调性可以将复杂度降为 O(N)。核心思想是对撞双指针：左右指针分别指向数组首尾。
面积由较短边决定。如果固定短边向内移动，高度不可能增加，面积只会减小或不变。因此，我们总是移动高度较小的那个指针，试图寻找更高的边来扩大面积。这样只需遍历一次即可找到最大值。
5. 有效三角形的个数 (Valid Triangle Number)
题目链接： LeetCode 611
构成三角形的条件是任意两边之和大于第三边。若数组已排序（a ≤ b ≤ c），只需验证 a + b > c 即可。
优化策略是先排序，然后固定最大边 c，用双指针 left 和 right 在剩余部分查找满足条件的组合。若 nums[left] + nums[right] > nums[c]，说明 left 到 right-1 之间的所有数与 right 都能组成三角形，直接累加计数，然后 right--；否则 left++。
6. 两数之和 II (Two Sum II)
题目链接： LeetCode 167
输入数组已排序，直接使用对撞双指针。左指针指向头，右指针指向尾，根据当前和与目标值的比较移动指针：和大则右移左指针，和小则右移右指针，相等则返回结果。时间复杂度 O(N)。
7. 三数之和 (3Sum)
题目链接： LeetCode 15
这是双指针的经典进阶应用。外层循环固定一个数 i，内层使用双指针寻找另外两个数。难点在于去重和边界处理。
- 去重： 如果
nums[i]与前一个相同，跳过；找到一组解后，left和right也要跳过重复值，避免重复三元组。 - 边界： 确保
left < right，防止越界。
def threeSum(nums):
nums.sort()
res = []
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i-1]: continue
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 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 s < 0: left += 1
else: right -= 1
return res
8. 四数之和 (4Sum)
题目链接： LeetCode 18
在三数之和的基础上多套一层循环。同样需要注意去重逻辑和溢出问题。由于四个数相加可能超出整型范围，求和时需强转为长整型（如 C++ 中的 long long）。
以上这些题目展示了双指针在不同场景下的变体：同向移动、对撞移动、快慢指针等。掌握其背后的单调性与空间划分思想，比死记硬背代码更重要。
