【橡皮思维】滑动窗口与双指针：用弹性边界降维打击

路飞的橡皮能力核心不是「拉伸」，而是「弹性边界」——他能把攻击范围在瞬间伸展到极限，又在恰当的时刻收回。双指针和滑动窗口的本质就是这个：用两个可移动的边界，把 O(n²) 的暴力枚举压缩成 O(n) 的线性扫描。

暴力解是用两个固定锚点对所有组合穷举；弹性边界是让两个锚点根据当前状态智能移动，每个元素最多被访问两次。

一、双指针

1.1 相向双指针

左右两端各放一个指针，根据条件向中间夹逼。适用场景：有序数组上的两数之和、最大面积、接雨水。

两数之和 II（LeetCode 167）

public int[] twoSum(int[] numbers, int target) {
    int l = 0, r = numbers.length - 1;
    while (l < r) {
        int sum = numbers[l] + numbers[r];
        if (sum == target)  return new int[]{l + 1, r + 1};
        if (sum < target)   l++;
        else                r--;
    }
    return new int[]{-1, -1};
}

为什么正确？因为数组有序，sum < target 时只有右移左指针才能让和变大；sum > target 时只有左移右指针才能让和变小。每步都在消除一个不可能的答案，不会漏解。

盛最多水的容器（LeetCode 11）

面积 = min(height[l], height[r]) × (r - l)。移动较高的那侧指针只会让宽度减小但高度不变或更低，面积必然不会更大；移动较矮的那侧才有机会找到更高的边界，面积可能增大。

public int maxArea(int[] height) {
    int l = 0, r = height.length - 1, ans = 0;
    while (l < r) {
        ans = Math.max(ans, Math.min(height[l], height[r]) * (r - l));
        if (height[l] < height[r]) l++;
        else                        r--;
    }
    return ans;
}

三数之和（LeetCode 15）

固定一个数，剩下两个用相向双指针。注意去重：外层循环跳过重复，内层找到答案后两侧同时跳过重复。

public List<List<Integer>> threeSum(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) continue; // 外层去重
        int l = i + 1, r = nums.length - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) {
                res.add(Arrays.asList(nums[i], nums[l], nums[r]));
                while (l < r && nums[l] == nums[l + 1]) l++; // 内层去重
                while (l < r && nums[r] == nums[r - 1]) r--;
                l++; r--;
            } else if (sum < 0) l++;
            else                r--;
        }
    }
    return res;
}

接雨水（LeetCode 42）

每个位置能接的水 = min(左侧最大高度, 右侧最大高度) - 当前高度。预处理左右最大值是 O(n) 空间的经典解，但双指针可以做到 O(1) 空间：

public int trap(int[] height) {
    int l = 0, r = height.length - 1;
    int leftMax = 0, rightMax = 0, ans = 0;
    while (l < r) {
        if (height[l] < height[r]) {
            if (height[l] >= leftMax) leftMax = height[l];
            else                      ans += leftMax - height[l];
            l++;
        } else {
            if (height[r] >= rightMax) rightMax = height[r];
            else                       ans += rightMax - height[r];
            r--;
        }
    }
    return ans;
}

关键推论：当 height[l] < height[r] 时，l 位置能接多少水只取决于 leftMax，因为右侧一定存在比 leftMax 更高的边界（即 height[r]）。反之同理。

1.2 快慢指针

两个指针同向移动，快指针先走，慢指针跟随或滞后。适用场景：链表中点、链表环检测、原地删除。

原地删除有序数组重复项（LeetCode 26）

public int removeDuplicates(int[] nums) {
    int slow = 0;
    for (int fast = 1; fast < nums.length; fast++) {
        if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast];
        }
    }
    return slow + 1;
}

slow 指向已处理区间的末尾，fast 负责探索新元素。每当 fast 找到不重复的值，slow 才往前走一步接收它。

链表环检测（LeetCode 141）

public 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;
}

快指针每次走 2 步，慢指针走 1 步。如果有环，快指针终会在环内追上慢指针，追及的相对速度是每轮缩短 1 步。

二、滑动窗口

双指针的同向变体。左右指针维护一个「窗口」，右指针扩张窗口纳入新元素，左指针收缩窗口排除不满足条件的元素。右指针只向右走，左指针只向右走，整体 O(n)。

2.1 固定窗口大小

大小为 k 的子数组最大平均值（LeetCode 643）

public double findMaxAverage(int[] nums, int k) {
    int windowSum = 0;
    for (int i = 0; i < k; i++) windowSum += nums[i];
    int maxSum = windowSum;
    for (int r = k; r < nums.length; r++) {
        windowSum += nums[r] - nums[r - k]; // 滑入右，滑出左
        maxSum = Math.max(maxSum, windowSum);
    }
    return (double) maxSum / k;
}

2.2 可变窗口大小

右指针先扩张，当窗口不再满足条件，左指针收缩到刚好满足为止。

无重复字符的最长子串（LeetCode 3）

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> freq = new HashMap<>();
    int l = 0, ans = 0;
    for (int r = 0; r < s.length(); r++) {
        freq.merge(s.charAt(r), 1, Integer::sum);
        while (freq.get(s.charAt(r)) > 1) {        // 有重复，收缩左边
            freq.merge(s.charAt(l), -1, Integer::sum);
            if (freq.get(s.charAt(l)) == 0) freq.remove(s.charAt(l));
            l++;
        }
        ans = Math.max(ans, r - l + 1);
    }
    return ans;
}

最小覆盖子串（LeetCode 76）

给定字符串 s 和 t，在 s 中找包含 t 所有字符的最短子串。

public String minWindow(String s, String t) {
    int[] need = new int[128], have = new int[128];
    int formed = 0, required = 0;
    for (char c : t.toCharArray()) {
        if (need[c]++ == 0) required++; // 需要 required 种字符都满足
    }
    int l = 0, minLen = Integer.MAX_VALUE, minL = 0;
    for (int r = 0; r < s.length(); r++) {
        char rc = s.charAt(r);
        have[rc]++;
        if (need[rc] > 0 && have[rc] == need[rc]) formed++;
        while (formed == required) {            // 窗口合法，尝试收缩
            if (r - l + 1 < minLen) { minLen = r - l + 1; minL = l; }
            char lc = s.charAt(l++);
            have[lc]--;
            if (need[lc] > 0 && have[lc] < need[lc]) formed--;
        }
    }
    return minLen == Integer.MAX_VALUE ? "" : s.substring(minL, minL + minLen);
}

formed 记录当前窗口已满足 t 中多少种字符的数量要求，等于 required 时窗口合法。

找到字符串中所有字母异位词（LeetCode 438）

固定窗口大小为 p.length()，判断窗口内字符频次是否与 p 相同。

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> res = new ArrayList<>();
    if (s.length() < p.length()) return res;
    int[] pCount = new int[26], wCount = new int[26];
    for (char c : p.toCharArray()) pCount[c - 'a']++;
    for (int r = 0; r < s.length(); r++) {
        wCount[s.charAt(r) - 'a']++;
        if (r >= p.length()) wCount[s.charAt(r - p.length()) - 'a']--;
        if (Arrays.equals(wCount, pCount)) res.add(r - p.length() + 1);
    }
    return res;
}

三、识别套路

特征	用哪种
有序数组，找两个数满足条件	相向双指针
链表找中点 / 判环 / 找倒数第 k 个	快慢指针
原地删除 / 移动元素	同向双指针（slow/fast）
子串 / 子数组，满足某条件的最长或最短	可变滑动窗口
固定长度子数组的统计值	固定滑动窗口

窗口何时该收缩？ 当窗口内的状态违反了约束（有重复字符、超出目标和、频次超标），就该移动左指针。如果是求最长则违反时收缩，如果是求最短则合法时就尝试收缩到不合法为止。

四、复杂度小结

技巧	时间	空间	对比暴力
相向双指针	O(n)	O(1)	暴力 O(n²)
快慢指针	O(n)	O(1)	—
固定滑动窗口	O(n)	O(1)	暴力 O(nk)
可变滑动窗口	O(n)	O(字符集)	暴力 O(n²)

路飞的橡皮手臂可以延伸到视线之外，但收回的速度同样快——右指针扩张从不回头，左指针收缩也从不回头，这就是线性复杂度的保证。每个元素最多被左指针和右指针各访问一次，共 2n 次操作。

下一站：风车村 · 【弹力延伸】二分查找的本质——把搜索空间对折再对折