two-pointers-and-sliding-window.md

title	双指针与滑动窗口面试题总结：数组、链表、字符串高频模板
description	双指针与滑动窗口面试题总结，讲解左右指针、快慢指针、读写指针、固定窗口、可变窗口、Java 模板和 LeetCode 高频题。
category	计算机基础
tag	算法
head	meta name content keywords 双指针,滑动窗口,快慢指针,左右指针,读写指针,固定窗口,可变窗口,数组算法,链表算法,字符串算法,LeetCode

双指针和滑动窗口经常放在一起复习，但它们解决的问题不完全一样。双指针更像一种移动策略，滑动窗口则强调维护一个连续区间里的状态。

一个实用判断：如果题目关心两个位置之间的关系，先想双指针；如果题目关心连续子数组或连续子串，并且窗口内有条件要维护，先想滑动窗口。

面试考察重点

• 能区分左右指针、快慢指针、读写指针。
• 能维护滑动窗口里的计数、和、最大值或匹配情况。
• 能解释为什么指针只向一个方向移动，时间复杂度是 O(n)。
• 能处理空数组、单元素、重复元素和窗口收缩边界。

两者到底有什么区别？

双指针是一种更宽泛的写法，只要用两个指针协作推进，都可以叫双指针。滑动窗口更具体，它维护的是一个连续区间 [left, right]，窗口里通常有一组状态，比如字符计数、元素和、最大值、匹配数量。

问题特征	更可能使用
有序数组里找两个数	左右指针
链表找环、找中点、找倒数第 K 个节点	快慢指针
原地删除或覆盖元素	读写指针
连续子数组/子串的最长、最短、计数	滑动窗口

面试时先把指针含义说出来，比直接写代码更稳。比如“left 表示窗口左边界，right 表示正在尝试加入窗口的字符”，后面收缩窗口就不会乱。

左右指针

左右指针常用于有序数组或两端收缩问题：

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

如果数组无序，通常先排序，再用左右指针。排序后要记得复杂度变成 O(nlogn)。

左右指针能工作的原因，是每次比较后可以排除一部分答案。以有序数组两数之和为例：

• 当前和太小，说明左指针指向的数太小，右指针再往左只会更小，所以只能左指针右移。
• 当前和太大，说明右指针指向的数太大，左指针再往右只会更大，所以只能右指针左移。

三数之和也是同一个思路，只是先固定一个数，再在剩余区间里做两数之和。难点在去重：固定数要去重，左右指针找到答案后也要跳过重复值。

快慢指针

快慢指针常用于链表：

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

链表题的重点不是代码长，而是指针含义稳定。fast != null && fast.next != null 的顺序也不能反。

快慢指针常见有两种速度差：

• fast 每次走 2 步，slow 每次走 1 步：用于环检测和找链表中点。
• 一个指针先走 k 步，另一个指针再一起走：用于找倒数第 k 个节点。

找倒数第 k 个节点时，两个指针之间保持 k 个节点的距离。当前面的指针走到链表末尾，后面的指针刚好停在目标位置。删除倒数第 N 个节点时，通常会加虚拟头节点，避免删除头节点时单独处理。

读写指针

读写指针常用于原地修改数组：

int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    int write = 1;
    for (int read = 1; read < nums.length; read++) {
        if (nums[read] != nums[read - 1]) {
            nums[write] = nums[read];
            write++;
        }
    }
    return write;
}

read 负责扫描原数组，write 指向下一个可写入位置。面试里最好先把这两个变量的含义说出来。

读写指针的核心是“读完整个数组，只把需要保留的内容写回前面”。这类题经常要求原地修改，返回新长度，而不是创建新数组。

判断写入时机时，可以问自己：当前 read 指向的元素是否应该保留？如果应该保留，就写到 write，然后 write++；如果不应该保留，只移动 read。

可变滑动窗口

以“无重复字符的最长子串”为例：

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

这个模板里，右指针负责扩大窗口，左指针负责在窗口不合法时收缩。每个字符最多进窗口一次、出窗口一次，所以时间复杂度是 O(n)。

可变窗口一般有一个固定节奏：

1. 右指针加入新元素，更新窗口状态。
2. 当窗口不满足条件时，不断移动左指针，并同步更新状态。
3. 在窗口满足题意的位置更新答案。

最长问题和最短问题的更新时机不一样：

• 求最长合法窗口：通常在窗口恢复合法后更新答案。
• 求最短满足条件窗口：通常在窗口已经满足条件时更新答案，然后继续收缩左边界。

比如“最小覆盖子串”里，窗口一旦覆盖了目标字符，就要先更新答案，再尝试缩小窗口；“最长无重复子串”里，窗口有重复字符时要先缩到合法，再更新答案。

固定滑动窗口

固定窗口适合“长度为 k 的子数组/子串”：

int maxSum(int[] nums, int k) {
    int window = 0;
    for (int i = 0; i < k; i++) {
        window += nums[i];
    }
    int ans = window;
    for (int right = k; right < nums.length; right++) {
        window += nums[right];
        window -= nums[right - k];
        ans = Math.max(ans, window);
    }
    return ans;
}

固定窗口的重点是右侧进一个元素，左侧出一个元素。

固定窗口不用 while 收缩，因为窗口长度始终固定。它更像一个滚动统计：

• 新元素进入窗口。
• 离开窗口的旧元素被移除。
• 更新当前窗口答案。

如果窗口里还要维护最大值或最小值，普通变量不够用，通常要用单调队列。比如“滑动窗口最大值”中，队列里存可能成为最大值的下标，队首就是当前窗口最大值。

面试手写路径

双指针和滑动窗口题，面试里最怕指针含义写到一半变了。建议按这个顺序写：

1. 先判断题型：是两端收缩、快慢追赶、原地覆盖，还是连续窗口。
2. 明确指针含义：left、right、slow、fast、write 分别指向哪里。
3. 明确窗口状态：窗口内维护的是和、计数、最大值，还是匹配数量。
4. 明确移动条件：什么时候右指针扩张，什么时候左指针收缩。
5. 明确答案更新时机：合法后更新最长，满足条件时更新最短。

一句话区分最长和最短：最长题通常先修复窗口再更新答案，最短题通常先记录答案再继续收缩。

代表题精讲：最小覆盖子串

76. 最小覆盖子串 是滑动窗口里最能考细节的一题。题目要求在 s 中找到最短子串，使它覆盖 t 中所有字符和对应次数。

这题的关键不是会不会用窗口，而是能不能说清两个计数：

• need：目标字符串 t 里每个字符需要多少个。
• window：当前窗口里每个字符已经有多少个。
• valid：有多少种字符已经满足所需次数。

当 valid == need.size() 时，说明当前窗口已经覆盖 t，这时要更新答案，并尝试收缩左边界。

String minWindow(String s, String t) {
    Map<Character, Integer> need = new HashMap<>();
    Map<Character, Integer> window = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }

    int left = 0;
    int valid = 0;
    int start = 0;
    int minLen = Integer.MAX_VALUE;

    for (int right = 0; right < s.length(); right++) {
        char in = s.charAt(right);
        if (need.containsKey(in)) {
            window.put(in, window.getOrDefault(in, 0) + 1);
            if (window.get(in).equals(need.get(in))) {
                valid++;
            }
        }

        while (valid == need.size()) {
            if (right - left + 1 < minLen) {
                start = left;
                minLen = right - left + 1;
            }
            char out = s.charAt(left);
            left++;
            if (need.containsKey(out)) {
                if (window.get(out).equals(need.get(out))) {
                    valid--;
                }
                window.put(out, window.get(out) - 1);
            }
        }
    }

    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

这里有两个容易写错的点：

• valid-- 要发生在减少 window[out] 之前，因为此时窗口还刚好满足条件。
• 更新答案要放在 while (valid == need.size()) 里面，因为只有当前窗口已经覆盖 t，才有资格参与最短答案比较。

过程示意和边界样例

以“无重复字符的最长子串”为例，字符串 abba 的窗口变化如下：

右指针字符	加入后窗口	是否合法	左指针怎么动	当前最长
a	a	合法	不动	1
b	ab	合法	不动	2
b	abb	不合法	移走 a 后仍不合法，再移走第一个 b	2
a	ba	合法	不动	2

滑动窗口建议至少检查这些边界：

输入	重点
空字符串或空数组	是否直接返回 0
全部字符相同	左边界是否持续收缩
没有重复字符	答案是否能更新到整个长度
最优窗口在开头或结尾	更新答案的时机是否正确

常见错误写法：

if (count.get(c) > 1) {
    left++; // 错：只移动一次不一定能恢复合法窗口
}

可变窗口收缩时通常要用 while，直到窗口重新满足条件。只移动一次，遇到 abba、aaabc 这类输入就容易错。

易错点

• 双指针题先明确两个指针的含义，不要边写边猜。
• 滑动窗口里，更新答案的时机要看题目问的是最长还是最短。
• 窗口收缩时，窗口内的计数、和、匹配数都要同步更新。
• 链表快慢指针要先判断 fast 和 fast.next。
• 三数之和这类题，排序后的去重要单独处理。

高频问题自测

• 为什么双指针题通常是 O(n)，而不是两层循环的 O(n^2)？
• 三数之和为什么需要排序？去重分别发生在哪几个位置？
• 快慢指针找链表中点时，偶数长度返回前中点还是后中点？
• 滑动窗口什么时候用 if 收缩，什么时候必须用 while 收缩？
• 最长窗口和最短窗口的答案更新时机有什么区别？

推荐练习题

• 26. 删除有序数组中的重复项
• 15. 三数之和
• 141. 环形链表
• 3. 无重复字符的最长子串
• 76. 最小覆盖子串