双指针与滑动窗口：用边界维护状态

这篇来自我补“双指针与滑动窗口：用边界维护状态”基础时的一次复盘。我之前的问题是：我最初把双指针和滑动窗口当成固定模板，真正写起来却总说不清到底该移动左边还是右边。等我把输入、状态变化和边界条件分别写出来之后，原来看似突然出现的规则就有了来路。

双指针和滑动窗口是数组、链表、字符串里非常高频的一类算法。它们解决的核心问题是：不要重复枚举所有组合，而是用两个边界维护当前状态。

很多暴力解法是两层循环，时间复杂度 O(n²)；双指针和滑动窗口经常能把它降到 O(n)。

它从哪里来

双指针和滑动窗口没有公认的单一发明者，它们是在顺序数据处理中逐步形成的通用技巧。核心演进是：不再为每个起点重复扫描，而是让边界单调移动，并复用上一个区间已经计算出的状态。

双指针的两种常见形态

双指针与滑动窗口

图：双指针通过移动边界减少重复枚举

第一种是相向双指针：一个从左往右，一个从右往左。

适合：

有序数组两数之和。
判断回文。
反转数组。
盛最多水的容器。

第二种是同向双指针：两个指针都往同一方向移动。

适合：

原地去重。
快慢指针。
链表环检测。
滑动窗口。

有序数组两数之和

暴力做法枚举所有两数组合是 O(n²)。如果数组有序，可以这样：

int[] twoSumSorted(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) return new int[]{left, right};
        if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return new int[]{-1, -1};
}

为什么这样不会漏答案？

如果当前和太小，说明 nums[left] 和任何比 right 更小的位置相加只会更小，所以 left 可以右移。如果当前和太大，说明 nums[right] 和任何比 left 更大的位置相加只会更大，所以 right 可以左移。

这里靠的是有序性。

快慢指针

快慢指针最经典的是链表环检测。

boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

如果链表有环，快指针每次比慢指针多走一步，最终会在环里追上。这个思想也能用来找链表中点、判断快乐数等问题。

滑动窗口是什么

滑动窗口本质是同向双指针，用 [left, right] 或 [left, right) 表示当前连续区间，并维护区间内的信息。

常见问题：

最长无重复子串。
最小覆盖子串。
长度为 k 的最大平均值。
连续子数组和。
固定窗口最大值。

滑动窗口最重要的是两个问题：

什么时候扩大窗口？
什么时候收缩窗口？

最长无重复子串

int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> window = new HashMap<>();
    int left = 0, ans = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        window.put(c, window.getOrDefault(c, 0) + 1);
        while (window.get(c) > 1) {
            char d = s.charAt(left++);
            window.put(d, window.get(d) - 1);
        }
        ans = Math.max(ans, right - left + 1);
    }
    return ans;
}

这里窗口内始终保持“没有重复字符”的不变量。当加入 right 后破坏了不变量，就移动 left 修复。

固定窗口和可变窗口

固定窗口比较简单，比如求长度为 k 的最大和：

int maxSumOfK(int[] nums, int k) {
    int sum = 0, ans = Integer.MIN_VALUE;
    for (int i = 0; i < nums.length; i++) {
        sum += nums[i];
        if (i >= k) sum -= nums[i - k];
        if (i >= k - 1) ans = Math.max(ans, sum);
    }
    return ans;
}

可变窗口更考验条件设计。一般套路是：右边界不断加入元素，直到窗口不满足条件，再移动左边界恢复条件。

常见错误

只会套模板，不知道窗口内维护的是什么状态。
忘记在左指针移动时同步更新计数。
把固定窗口和可变窗口混用。
双指针移动依据不成立，导致漏答案。
链表快慢指针忘记判断 fast.next。

工程场景

双指针和滑动窗口在工程中很常见：

日志流里统计最近 5 分钟请求量。
限流器维护时间窗口内的访问次数。
字符串扫描、敏感词预处理。
实时指标计算中的滑动统计。
有序数据合并、去重、交集计算。

算法题里的窗口通常在数组上，工程里的窗口经常在时间线上，但思想一致：维护一段当前有效的范围。

面试题

双指针为什么能降低复杂度？
相向双指针必须依赖有序性吗？
滑动窗口和双指针是什么关系？
最长窗口和最短窗口的收缩策略有什么不同？
快慢指针为什么能判断链表是否有环？

小结

双指针不是“两根指针”这么简单，而是用边界表达状态。滑动窗口则是在连续区间里维护计数、和、最大值、频率等信息。它们的关键是移动依据必须正确，否则看起来很优雅，实际会偷偷漏答案。