双指针与滑动窗口技巧详解

这些技巧解决什么问题

许多数组和字符串问题问的是数对或连续区间：和为目标值的两个数、不含重复字符的最长子串、和不小于 k 的最短子数组。检查每一个数对或每一段区间，代价是 O(n²) 甚至更高。双指针利用数据的某种性质（比如有序，或者窗口每次只需做很小的更新），一次排除大量候选，从而避免这种代价。

两端指针：有序数组中的两数之和

在有序列表 [1, 3, 4, 6, 8, 11] 中找出和为 10 的两个数。从最小和最大的数开始。如果和太小，增大它的唯一办法是把 left 右移；如果和太大，就把 right 左移。

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return None
print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))   # (2, 3)
print(pair_with_sum([1, 3, 4, 6, 8, 11], 2))    # None

每一步都让一个指针向内移动，所以最多 n − 1 步：时间 O(n)，空间 O(1)。同样的写法还可用来判断字符串是否为回文、原地反转数组，并且嵌套在外层循环中时，能把三数之和从 O(n³) 降到 O(n²)。

快慢指针：原地过滤

慢指针标记下一个保留元素应放的位置；快指针扫描每个元素。这样可以在不使用额外内存的情况下，为有序列表去重。

def dedupe_sorted(nums):
    """Remove duplicates in place; return the new length."""
    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
a = [1, 1, 2, 3, 3, 3, 5]
k = dedupe_sorted(a)
print(k, a[:k])   # 4 [1, 2, 3, 5]

在链表上，快指针每步走两个节点，慢指针每步走一个。如果两者相遇，说明链表有环（Floyd 判圈算法）；当快指针到达末尾时，慢指针正好在中点。

滑动窗口：无重复字符的最长子串

滑动窗口始终保证区间 s[left:right + 1] 是合法的。让 right 每次前进一个字符。当新字符破坏了规则，就前移 left，直到窗口重新合法。边走边记录最优的窗口。

def longest_unique(s):
    last_seen = {}          # char -> last index
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1   # jump past the repeat
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best
print(longest_unique("abcabcbb"))   # 3  ("abc")
print(longest_unique("pwwkew"))     # 3  ("wke")
print(longest_unique(""))           # 0

窗口分为两种。固定大小的窗口含 k 个元素，每次加入右侧进来的元素，并移除左侧离开的元素，例如用来计算移动平均。可变大小的窗口则通过扩大和收缩来满足某个条件，如上面的例子。

def min_len_subarray(nums, k):
    """Shortest subarray with sum >= k (non-negative nums)."""
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= k:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best
print(min_len_subarray([2, 3, 1, 2, 4, 3], 7))   # 2  ([4, 3])

时间与空间复杂度

即使带有嵌套的 while 循环，滑动窗口仍是 O(n) 的原因在于：left 和 right 各自累计最多前移 n 次，所以总工作量至多 2n 步。

常见误区

• 在无序数据上使用两端指针。只有因为数组有序，决定移动 left 还是 right 才是正确的。
• 数字可能为负时仍使用基于和的滑动窗口。此时收缩窗口不一定会让和变小；应改用前缀和加哈希表。
• 窗口长度差一：闭区间 left..right 的窗口含有 right - left + 1 个元素。
• 忘记以 left < right 作为终止条件，会让单个元素与自己配成一对。
• 让 left 往回走。在子串的例子中，last_seen[ch] >= left 这个检查可防止跳回旧位置。

何时使用，以及典型面试题

当输入有序（或能低成本排序）并且要找数对，或者需要原地修改数组时，就用双指针。当题目提到连续子数组或子串，并要求在窗口增长时条件呈可预测变化的前提下求最长、最短、最大或计数，就用滑动窗口。如果数据无序又要找数对，哈希集合通常更简单，同样是 O(n)。

• Two Sum II（有序输入）、3Sum、Container With Most Water、Trapping Rain Water。
• Valid Palindrome、Reverse String、Move Zeroes、Remove Duplicates from Sorted Array。
• Longest Substring Without Repeating Characters、Minimum Window Substring、Sliding Window Maximum（配合双端队列）。
• Linked List Cycle、Middle of the Linked List。

在面试之外，同样的思路还出现在合并有序文件、跟踪未确认数据包窗口的网络协议（TCP 滑动窗口）、统计最近 N 秒内事件数的限流器，以及时间序列的移动平均中。