跳到主要内容

滑动窗口与双指针

双指针（Two Pointers）和滑动窗口（Sliding Window）是处理数组和字符串问题的利器，能够有效降低时间复杂度（通常从 O(n²) 降到 O(n)）。

双指针 Two Pointers​

1. 左右指针 (对撞指针)​

在有序数组中，一个从头开始，一个从尾开始，向中间靠拢。

适用场景：二分查找、两数之和、反转数组。

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

2. 快慢指针​

两个指针以不同的速度移动。

适用场景：链表是否有环、寻找链表中点、删除数组重复项。

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

滑动窗口 Sliding Window​

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

核心模板​

public void slidingWindow(String s) {
    int left = 0, right = 0;
    while (right < s.length()) {
        char c = s.charAt(right);
        // 增大窗口，并进行一系列更新
        right++;
        
        while (窗口需要收缩) {
            char d = s.charAt(left);
            // 缩小窗口，并进行一系列更新
            left++;
        }
    }
}

经典实例：最小覆盖子串 (LeetCode 76)​

给定 SS 和 TT，寻找包含 TT 所有字符的最短子串。

  1. right 延伸直到满足条件。
  2. left 收缩直到不再满足，记录最小长度。

练习​

  1. LeetCode 3：无重复字符的最长子串
  2. LeetCode 167：两数之和 II
  3. LeetCode 141/142：环形链表
  4. LeetCode 27：移除元素
  5. LeetCode 209：长度最小的子数组
  6. LeetCode 438：找到字符串中所有字母异位词