跳到主要内容

滑动窗口与双指针

双指针和滑动窗口是解决数组、字符串子区间问题的利器。它们能够将暴力解法中 O(n2)O(n^2) 甚至更高的时间复杂度优化到 O(n)O(n)，是面试中必会的技巧。

双指针技术​

双指针是指在遍历过程中使用两个指针协同工作，根据指针移动方式的不同，可以分为几种类型。

对撞指针（左右指针）​

对撞指针从数组两端向中间移动，一个从头开始（左指针），一个从尾开始（右指针）。

适用场景​

  • 有序数组的两数之和
  • 反转数组/字符串
  • 判断回文串
  • 接雨水问题
  • 容器盛水问题

经典示例：两数之和 II​

在有序数组中找到两个数，使它们的和等于目标值。

/**
 * 两数之和 II - 输入有序数组
 * LeetCode 167
 * 时间复杂度: O(n)
 * 空间复杂度: O(1)
 */
public int[] twoSum(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        
        if (sum == target) {
            return new int[]{left + 1, right + 1};  // 题目要求 1-indexed
        } else if (sum < target) {
            left++;   // 和太小，左指针右移
        } else {
            right--;  // 和太大，右指针左移
        }
    }
    
    return new int[]{-1, -1};  // 未找到
}

为什么这样正确？

数组有序是关键。当 numbers[left] + numbers[right] < target 时，numbers[left] 与任何更左边的数相加只会更小，所以可以安全地排除 left，将其右移。同理，当和大于目标时，可以排除 right。

经典示例：反转字符串​

/**
 * 原地反转字符串
 * 时间复杂度: O(n)
 * 空间复杂度: O(1)
 */
public void reverseString(char[] s) {
    int left = 0;
    int right = s.length - 1;
    
    while (left < right) {
        // 交换左右指针处的字符
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        
        left++;
        right--;
    }
}

经典示例：验证回文串​

/**
 * 验证字符串是否为回文串
 * 忽略非字母数字字符，忽略大小写
 * 时间复杂度: O(n)
 */
public boolean isPalindrome(String s) {
    int left = 0;
    int right = s.length() - 1;
    
    while (left < right) {
        // 跳过非字母数字字符
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
            left++;
        }
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
            right--;
        }
        
        // 比较（忽略大小写）
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        
        left++;
        right--;
    }
    
    return true;
}

经典示例：盛最多水的容器​

给定 nn 个非负整数表示每个点的高度，找出两条线使得它们与 x 轴构成的容器能盛最多的水。

/**
 * 盛最多水的容器
 * LeetCode 11
 * 
 * 核心思想：面积 = min(height[left], height[right]) * (right - left)
 * 移动较矮的指针，因为只有移动它才可能找到更高的柱子，从而可能增大面积
 */
public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int maxArea = 0;
    
    while (left < right) {
        // 计算当前面积
        int width = right - left;
        int currentHeight = Math.min(height[left], height[right]);
        int area = width * currentHeight;
        
        maxArea = Math.max(maxArea, area);
        
        // 移动较矮的指针
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxArea;
}

为什么移动较矮的指针？

面积由较矮的柱子决定。如果移动较高的柱子，宽度减小，高度不变（还是由较矮柱子决定），面积必然减小。只有移动较矮的柱子，才有可能遇到更高的柱子，从而可能增加面积。

快慢指针​

快慢指针以不同的速度移动，常用于处理链表问题和某些数组问题。

适用场景​

  • 判断链表是否有环
  • 找到链表的中间节点
  • 找到链表环的入口
  • 删除数组中的重复元素
  • 寻找重复数

经典示例：判断链表是否有环​

/**
 * 环形链表检测
 * LeetCode 141
 * 时间复杂度: O(n)
 * 空间复杂度: O(1)
 */
public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    
    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;
}

为什么快慢指针能检测环？

想象在跑道上跑步，如果跑道是环形的，跑得快的人一定会追上跑得慢的人（套圈）。如果跑道没有环，跑得快的人会先到达终点。

经典示例：找到链表中间节点​

/**
 * 找到链表的中间节点
 * 如果链表长度为偶数，返回第二个中间节点
 * LeetCode 876
 */
public ListNode middleNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;       // 慢指针走一步
        fast = fast.next.next;  // 快指针走两步
    }
    
    return slow;  // 慢指针指向中间节点
}

经典示例：找到环的入口​

/**
 * 环形链表 II - 找到环的入口节点
 * LeetCode 142
 * 
 * 数学推导：
 * 设环外长度为 a，环内相遇点距环入口为 b，环长度为 c
 * 快指针走了 a + n*c + b，慢指针走了 a + b
 * 由于快指针是慢指针的两倍：a + n*c + b = 2*(a + b)
 * 化简得：a = n*c - b = (n-1)*c + (c - b)
 * 这意味着从相遇点和起点同时出发，相遇点就是环入口
 */
public ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    
    // 第一阶段：找到相遇点
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow == fast) {
            // 第二阶段：找到环入口
            ListNode ptr1 = head;
            ListNode ptr2 = slow;
            
            while (ptr1 != ptr2) {
                ptr1 = ptr1.next;
                ptr2 = ptr2.next;
            }
            
            return ptr1;
        }
    }
    
    return null;  // 无环
}

快慢指针应用于数组​

经典示例：移除元素​

原地移除数组中等于给定值的所有元素，返回新长度。

/**
 * 移除元素
 * LeetCode 27
 * 
 * 思路：慢指针指向下一个有效元素应该放置的位置
 * 快指针遍历数组，找到有效元素
 */
public int removeElement(int[] nums, int val) {
    int slow = 0;  // 慢指针：下一个有效元素的位置
    
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    
    return slow;  // 新长度
}

经典示例：删除有序数组中的重复项​

/**
 * 删除有序数组中的重复项
 * LeetCode 26
 * 
 * 思路：慢指针指向唯一元素的最后位置
 * 快指针遍历寻找新的唯一元素
 */
public int removeDuplicates(int[] nums) {
    if (nums.length == 0) {
        return 0;
    }
    
    int slow = 0;  // 慢指针：唯一元素的末尾位置
    
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            slow++;
            nums[slow] = nums[fast];
        }
    }
    
    return slow + 1;  // 新长度
}

滑动窗口技术​

滑动窗口可以看作是双指针的特殊应用：右指针负责扩展窗口，左指针负责收缩窗口，维护窗口内的某种性质。

核心思想​

滑动窗口将嵌套循环问题转化为单循环问题：

// 暴力解法
for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
        // 处理区间 [i, j]
    }
}

// 滑动窗口
int left = 0;
for (int right = 0; right < n; right++) {
    // 扩展窗口
    while (需要收缩) {
        // 收缩窗口
        left++;
    }
}

滑动窗口模板​

/**
 * 滑动窗口通用模板
 */
public void slidingWindowTemplate(String s) {
    // 使用哈希表或其他数据结构记录窗口状态
    Map<Character, Integer> window = new HashMap<>();
    
    int left = 0;  // 窗口左边界
    int right = 0; // 窗口右边界
    
    while (right < s.length()) {
        // 获取要加入窗口的字符
        char c = s.charAt(right);
        
        // 扩展窗口：加入右侧元素
        window.put(c, window.getOrDefault(c, 0) + 1);
        right++;
        
        // 判断是否需要收缩窗口
        while (needShrink(window)) {
            // 获取要移出窗口的字符
            char d = s.charAt(left);
            
            // 收缩窗口：移出左侧元素
            window.put(d, window.get(d) - 1);
            if (window.get(d) == 0) {
                window.remove(d);
            }
            left++;
        }
        
        // 更新答案（在窗口满足条件时）
        // updateResult();
    }
}

经典示例：无重复字符的最长子串​

找出不含有重复字符的最长子串的长度。

/**
 * 无重复字符的最长子串
 * LeetCode 3
 * 时间复杂度: O(n)
 * 空间复杂度: O(min(m, n))，m 为字符集大小
 */
public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> charIndex = new HashMap<>();
    
    int maxLength = 0;
    int left = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        
        // 如果字符已在窗口中，移动左边界
        if (charIndex.containsKey(c) && charIndex.get(c) >= left) {
            left = charIndex.get(c) + 1;
        }
        
        // 更新字符位置
        charIndex.put(c, right);
        
        // 更新最大长度
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

经典示例：最小覆盖子串​

找出 ss 中涵盖 tt 所有字符（包括重复字符）的最小子串。

/**
 * 最小覆盖子串
 * LeetCode 76
 * 时间复杂度: O(|s| + |t|)
 * 空间复杂度: O(|s| + |t|)
 */
public String minWindow(String s, String t) {
    if (s.length() < t.length()) {
        return "";
    }
    
    // 统计 t 中各字符的需求
    Map<Character, Integer> need = new HashMap<>();
    for (char c : t.toCharArray()) {
        need.put(c, need.getOrDefault(c, 0) + 1);
    }
    
    // 窗口中的字符计数
    Map<Character, Integer> window = new HashMap<>();
    
    int left = 0;
    int valid = 0;  // 已满足需求的字符种类数
    
    // 记录最小覆盖子串的起始位置和长度
    int start = 0;
    int minLen = Integer.MAX_VALUE;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        
        // 扩展窗口
        if (need.containsKey(c)) {
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (window.get(c).equals(need.get(c))) {
                valid++;
            }
        }
        
        // 收缩窗口
        while (valid == need.size()) {
            // 更新最小子串
            if (right - left + 1 < minLen) {
                start = left;
                minLen = right - left + 1;
            }
            
            char d = s.charAt(left);
            left++;
            
            if (need.containsKey(d)) {
                if (window.get(d).equals(need.get(d))) {
                    valid--;
                }
                window.put(d, window.get(d) - 1);
            }
        }
    }
    
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

经典示例：长度最小的子数组​

找出数组中连续元素之和大于等于目标值的最小子数组长度。

/**
 * 长度最小的子数组
 * LeetCode 209
 * 时间复杂度: O(n)
 */
public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int sum = 0;
    int minLen = Integer.MAX_VALUE;
    
    for (int right = 0; right < nums.length; right++) {
        sum += nums[right];
        
        // 当和 >= target 时，尝试收缩窗口
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }
    
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

经典示例：找到字符串中所有字母异位词​

找出 ss 中所有 pp 的异位词（排列相同）的起始索引。

/**
 * 找到字符串中所有字母异位词
 * LeetCode 438
 * 时间复杂度: O(|s| + |p|)
 */
public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    
    if (s.length() < p.length()) {
        return result;
    }
    
    // 统计 p 中各字符的数量
    int[] need = new int[26];
    for (char c : p.toCharArray()) {
        need[c - 'a']++;
    }
    
    // 窗口中的字符计数
    int[] window = new int[26];
    
    int left = 0;
    int right = 0;
    int valid = 0;  // 匹配的字符种类数
    
    while (right < s.length()) {
        char c = s.charAt(right);
        right++;
        
        // 扩展窗口
        int idx = c - 'a';
        if (need[idx] > 0) {
            window[idx]++;
            if (window[idx] == need[idx]) {
                valid++;
            }
        }
        
        // 当窗口大小等于 p 的长度时，判断并收缩
        if (right - left == p.length()) {
            // 检查是否为异位词
            if (valid == countNonZero(need)) {
                result.add(left);
            }
            
            // 收缩窗口
            char d = s.charAt(left);
            left++;
            
            int idx2 = d - 'a';
            if (need[idx2] > 0) {
                if (window[idx2] == need[idx2]) {
                    valid--;
                }
                window[idx2]--;
            }
        }
    }
    
    return result;
}

private int countNonZero(int[] arr) {
    int count = 0;
    for (int n : arr) {
        if (n > 0) count++;
    }
    return count;
}

技巧总结​

双指针适用场景判断​

问题特征推荐方法典型题目
有序数组 + 两数之和对撞指针LeetCode 167
链表相关问题快慢指针LeetCode 141, 142, 876
原地修改数组快慢指针LeetCode 26, 27
反转/回文对撞指针LeetCode 125, 344
容器/面积问题对撞指针LeetCode 11, 42

滑动窗口适用场景判断​

问题特征典型题目
子串/子数组的连续区间LeetCode 3, 209
包含/排除某些元素LeetCode 76, 438
区间最值/求和LeetCode 239, 209
固定窗口大小LeetCode 438, 567

常见错误​

  1. 忘记收缩窗口：窗口满足条件后要持续收缩，而不是只收缩一次
  2. 边界条件处理：空字符串、单个字符等特殊情况
  3. 索引计算错误：right - left + 1 还是 right - left
  4. 哈希表更新顺序：先检查再更新，避免误判

小结​

双指针和滑动窗口的核心要点：

技巧时间优化核心思想
对撞指针O(n2)→O(n)O(n²) \to O(n)利用有序性或对称性
快慢指针O(n)→O(n)O(n) \to O(n)不同速度制造差异
滑动窗口O(n2)→O(n)O(n²) \to O(n)维护区间性质，增量更新

使用建议：

  • 遇到子区间/子串问题，首先考虑滑动窗口
  • 有序数组问题，考虑对撞指针
  • 链表问题，考虑快慢指针
  • 需要原地修改，考虑快慢指针

练习​

基础：

  1. LeetCode 167：两数之和 II
  2. LeetCode 141：环形链表
  3. LeetCode 876：链表的中间节点
  4. LeetCode 27：移除元素
  5. LeetCode 3：无重复字符的最长子串

进阶： 6. LeetCode 11：盛最多水的容器 7. LeetCode 42：接雨水（双指针） 8. LeetCode 15：三数之和（排序 + 双指针） 9. LeetCode 76：最小覆盖子串 10. LeetCode 209：长度最小的子数组

挑战： 11. LeetCode 239：滑动窗口最大值（单调队列） 12. LeetCode 424：替换后的最长重复字符 13. LeetCode 567：字符串的排列 14. LeetCode 438：找到字符串中所有字母异位词 15. LeetCode 713：乘积小于 K 的子数组