用两个指针在数组上跳舞，将O(n²)暴力法变为O(n)优雅解
双指针（Two Pointers）是一种通过两个指针在数据结构上协同移动来解决问题的技巧。根据指针移动方向的不同，可分为对撞指针和快慢指针两大类。双指针能将许多 O(n²) 的问题优化为 O(n)，是面试中出现频率极高的技巧。
| 信号 | 推荐指针类型 | 示例题目 |
|---|---|---|
| 有序数组找配对 | 对撞指针 | LC 167, LC 11 |
| 原地删除/去重 | 快慢指针 | LC 26, LC 27 |
| 连续子数组问题 | 滑动窗口 | LC 3, LC 76 |
| 链表环检测 | 快慢指针 | LC 141, LC 142 |
| n数之和 | 对撞+固定 | LC 15, LC 18 |
题目描述：给定一个长度为 n 的整数数组 height，有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
class Solution:
def maxArea(self, height: List[int]) -> int:
left, right = 0, len(height) - 1
max_area = 0
while left < right:
width = right - left
h = min(height[left], height[right])
max_area = max(max_area, width * h)
if height[left] < height[right]:
left += 1
else:
right -= 1
return max_area时间复杂度：O(n) — 两个指针各最多移动 n 次
空间复杂度：O(1) — 只用常数变量
题目描述：给你一个整数数组 nums，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ≠ j ≠ k 且 nums[i] + nums[j] + nums[k] = 0。请你返回所有不重复的三元组。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
n = len(nums)
result = []
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
if nums[i] > 0:
break
left, right = i + 1, n - 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时间复杂度：O(n²) — 外层 O(n)，内层双指针 O(n)
空间复杂度：O(1) — 排序是原地的
题目描述：给你一个非严格递增排列的数组 nums，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
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时间复杂度：O(n) — fast 指针遍历一次
空间复杂度：O(1) — 原地修改