本文详细介绍了两种重要的算法技巧：滑动窗口和双指针。这些技巧广泛用于优化数组和字符串问题的解决方案，通常能将时间复杂度从 O(n²) 降低到 O(n)。本页将重点介绍这些技巧的基本概念、实现模式以及在编码面试和算法问题中的常见应用。
滑动窗口和双指针是相关的算法模式，通过最小化冗余操作来高效地处理数组、字符串和链表。
来源： problems/11.container-with-most-water.md36-113 problems/26.remove-duplicates-from-sorted-array.md60-74
双指针技术涉及使用两个参考点来高效地遍历数组或序列。这种方法特别适用于涉及排序数组、回文或寻找具有特定属性的对的问题。
来源： problems/26.remove-duplicates-from-sorted-array.md76-74 problems/283.move-zeroes.md35-44 problems/167.two-sum-ii-input-array-is-sorted.md38-46
这种方法使用两个从数组两端开始，通常朝着彼此移动，直到它们相遇或满足某个条件。
来源： problems/11.container-with-most-water.md65-72 problems/167.two-sum-ii-input-array-is-sorted.md106-146
左右指针方法用于寻找最大的盛水容器
来源： problems/11.container-with-most-water.md85-113
在此问题中，关键的见解是面积由两个高度中较小的一个决定，因此我们始终将较小高度的指针向内移动，以尝试找到更大的面积。
快慢指针技术使用两个以不同速度遍历序列的指针，通常用于检测循环或查找中间元素。
在这种方法中，一个指针遍历数组，而另一个指针负责写入（或修改）元素。
来源： problems/26.remove-duplicates-from-sorted-array.md103-110 problems/283.move-zeroes.md60-72
读写指针用于就地删除重复项
来源： problems/26.remove-duplicates-from-sorted-array.md100-111
滑动窗口技术是一种将两个嵌套循环转换为单个循环的方法，它通过维护一个“窗口”元素并将该窗口在数组或字符串中滑动来实现。
来源： problems/220.contains-duplicate-iii.md84-117
来源： problems/219.contains-duplicate-ii.md38-42 problems/220.contains-duplicate-iii.md102-113
此问题使用了固定大小的滑动窗口方法
来源： problems/219.contains-duplicate-ii.md63-74
滑动窗口技术可以被视为双指针技术的一种特殊应用。在滑动窗口中，两个指针通常定义当前窗口的边界。
来源： problems/220.contains-duplicate-iii.md102-113
来源： problems/26.remove-duplicates-from-sorted-array.md60-74 problems/283.move-zeroes.md35-44
来源： problems/167.two-sum-ii-input-array-is-sorted.md38-46 problems/11.container-with-most-water.md36-72
来源： problems/219.contains-duplicate-ii.md38-42 problems/220.contains-duplicate-iii.md84-117
left = 0, right = array.length - 1
while left < right:
if condition_met(array[left], array[right]):
process_result()
if move_left_condition:
left++
else:
right--
来源： problems/167.two-sum-ii-input-array-is-sorted.md147-158
slow = 0
for fast in range(array.length):
if condition(array[fast]):
process(slow, fast)
slow++
来源： problems/26.remove-duplicates-from-sorted-array.md94-113
left = 0
for right in range(array.length):
add array[right] to window
while window_condition_invalid:
remove array[left] from window
left++
update_result_if_needed()
来源： problems/219.contains-duplicate-ii.md63-74
在实现这些技术时，请注意
来源： problems/26.remove-duplicates-from-sorted-array.md102 problems/11.container-with-most-water.md91
| 问题类型 | 技术 | 示例问题 | 时间复杂度 | 空间复杂度 |
|---|---|---|---|---|
| 有序数组对查找 | 左右指针 | 两数之和 II | O(n) | O(1) |
| 容器优化 | 左右指针 | 盛最多水的容器 | O(n) | O(1) |
| 原地去重 | 快慢指针 | 删除有序数组中的重复项 | O(n) | O(1) |
| 原地元素移动 | 读写指针 | 移动零 | O(n) | O(1) |
| 固定窗口去重 | 滑动窗口 | 存在重复元素 II | O(n) | O(min(n,k)) |
| 有界差值 | 滑动窗口 + 桶 | 存在重复元素 III | O(n) | O(min(n,k)) |
| 回文扩展 | 双指针扩展 | 最长回文子串 | O(n²) | O(1) |
来源： problems/167.two-sum-ii-input-array-is-sorted.md160-163 problems/11.container-with-most-water.md150-153 problems/26.remove-duplicates-from-sorted-array.md170-173 problems/283.move-zeroes.md139-142 problems/219.contains-duplicate-ii.md131-134 problems/220.contains-duplicate-iii.md183-187 problems/5.longest-palindromic-substring.md159-162
滑动窗口和双指针技术是优化数组和字符串算法的强大工具。理解何时以及如何应用这些技术可以显著提高解决方案的效率。请记住以下关键点：
有关这些技术的更多高级算法，请参阅 动态规划 页面，因为许多滑动窗口问题也可以使用 DP 方法解决。