LeetCode双指针与滑动窗口算法全解析：从基础到高级应用

安全风信子

发布于 2025-11-13 13:21:14

910

文章被收录于专栏：AI SPPECHAI SPPECH

一、双指针算法基础

1.1 双指针算法的基本概念

双指针算法是一种在数组或链表中使用两个指针来解决问题的方法。这两个指针可以同向移动，也可以反向移动，具体取决于问题的需求。双指针算法通常可以将时间复杂度从O(n²)降低到O(n)，空间复杂度从O(n)降低到O(1)。

双指针算法的核心思想是：通过两个指针的移动，减少不必要的遍历，从而提高算法的效率。

1.2 双指针算法的分类

根据两个指针的移动方向，双指针算法可以分为以下几类：

同向双指针：两个指针都朝同一个方向移动
- 快慢指针（Fast-Slow Pointers）：一个指针移动得快，另一个指针移动得慢
- 滑动窗口（Sliding Window）：两个指针都朝同一个方向移动，形成一个窗口
反向双指针：两个指针朝相反的方向移动
- 左右指针（Left-Right Pointers）：一个指针从数组的左端开始，另一个指针从数组的右端开始，向中间移动

1.3 双指针算法的应用场景

双指针算法常用于解决以下几类问题：

链表问题：判断链表是否有环、寻找链表的中点、寻找链表的倒数第k个节点等
数组问题：两数之和、三数之和、移除元素、有序数组的平方等
字符串问题：反转字符串、回文串判断、最长回文子串等
滑动窗口问题：最长无重复字符子串、最小覆盖子串、滑动窗口最大值等

1.4 双指针算法的时间和空间复杂度

双指针算法的时间复杂度通常是O(n)，其中n是数组或链表的长度，因为每个元素最多被访问一次。

双指针算法的空间复杂度通常是O(1)，因为它只需要使用有限的额外空间来存储两个指针。

二、同向双指针：快慢指针

2.1 链表中找环（LeetCode 141）

题目描述：给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。

示例：输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。

解题思路：我们可以使用快慢指针来解决这个问题。快指针每次移动两步，慢指针每次移动一步。如果链表中有环，那么快指针最终会追上慢指针；如果链表中没有环，那么快指针最终会到达链表的末尾（即next为null）。

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

2.2 链表的中间结点（LeetCode 876）

题目描述：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。

示例：输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5])

解题思路：我们可以使用快慢指针来解决这个问题。快指针每次移动两步，慢指针每次移动一步。当快指针到达链表的末尾时，慢指针正好指向链表的中间节点。

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

2.3 移除链表元素（LeetCode 203）

题目描述：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。

示例：输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

解题思路：我们可以使用两个指针来解决这个问题。一个指针（prev）指向当前处理节点的前一个节点，另一个指针（curr）指向当前处理的节点。当curr指向的节点的值等于val时，我们删除该节点，即将prev的next指向curr的next；否则，我们将prev和curr都向前移动一位。

public ListNode removeElements(ListNode head, int val) {
    // 处理头节点的值等于val的情况
    while (head != null && head.val == val) {
        head = head.next;
    }
    if (head == null) {
        return null;
    }
    ListNode prev = head;
    ListNode curr = head.next;
    while (curr != null) {
        if (curr.val == val) {
            // 删除当前节点
            prev.next = curr.next;
        } else {
            // 只有当不删除当前节点时，才移动prev指针
            prev = curr;
        }
        // 无论是否删除当前节点，都移动curr指针
        curr = curr.next;
    }
    return head;
}

2.4 删除排序链表中的重复元素（LeetCode 83）

题目描述：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例：输入：1->1->2 输出：1->2

解题思路：我们可以使用两个指针来解决这个问题。一个指针（prev）指向当前处理节点的前一个节点，另一个指针（curr）指向当前处理的节点。当curr指向的节点的值等于prev指向的节点的值时，我们删除curr指向的节点；否则，我们将prev和curr都向前移动一位。

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode prev = head;
    ListNode curr = head.next;
    while (curr != null) {
        if (curr.val == prev.val) {
            // 删除当前节点
            prev.next = curr.next;
        } else {
            // 只有当不删除当前节点时，才移动prev指针
            prev = curr;
        }
        // 无论是否删除当前节点，都移动curr指针
        curr = curr.next;
    }
    return head;
}

三、反向双指针：左右指针

3.1 反转字符串（LeetCode 344）

题目描述：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例：输入：[“h”,“e”,“l”,“l”,“o”] 输出：[“o”,“l”,“l”,“e”,“h”]

解题思路：我们可以使用两个指针来解决这个问题。一个指针（left）从数组的左端开始，另一个指针（right）从数组的右端开始，向中间移动。在移动的过程中，交换两个指针指向的字符。

public void reverseString(char[] s) {
    int left = 0;
    int right = s.length - 1;
    while (left < right) {
        // 交换left和right指向的字符
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        // 移动指针
        left++;
        right--;
    }
}

3.2 两数之和 II - 输入有序数组（LeetCode 167）

题目描述：给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

示例：输入：numbers = [2,7,11,15], target = 9 输出：[1,2] 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

解题思路：我们可以使用两个指针来解决这个问题。一个指针（left）从数组的左端开始，另一个指针（right）从数组的右端开始，向中间移动。如果两个指针指向的数的和等于目标数，那么我们找到了答案；如果两个指针指向的数的和小于目标数，那么我们将left向右移动一位；如果两个指针指向的数的和大于目标数，那么我们将right向左移动一位。

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) {
            // 注意：题目要求的下标是从1开始的
            return new int[]{left + 1, right + 1};
        } else if (sum < target) {
            // 如果和小于目标数，将left向右移动一位
            left++;
        } else {
            // 如果和大于目标数，将right向左移动一位
            right--;
        }
    }
    // 如果没有找到答案，返回一个空数组
    return new int[0];
}

3.3 验证回文串（LeetCode 125）

题目描述：给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

示例：输入：“A man, a plan, a canal: Panama” 输出：true 解释：“amanaplanacanalpanama” 是回文串

解题思路：我们可以使用两个指针来解决这个问题。一个指针（left）从字符串的左端开始，另一个指针（right）从字符串的右端开始，向中间移动。在移动的过程中，跳过非字母和数字的字符，然后比较两个指针指向的字符是否相同（忽略大小写）。

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

3.4 盛最多水的容器（LeetCode 11）

题目描述：给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

示例：输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

解题思路：我们可以使用两个指针来解决这个问题。一个指针（left）从数组的左端开始，另一个指针（right）从数组的右端开始，向中间移动。容器的面积等于两个指针指向的数的较小值乘以两个指针之间的距离。在移动的过程中，我们总是移动指向较小值的指针，因为这样可以尝试寻找更大的面积。

public int maxArea(int[] height) {
    int left = 0;
    int right = height.length - 1;
    int maxArea = 0;
    while (left < right) {
        // 计算当前容器的面积
        int currentArea = Math.min(height[left], height[right]) * (right - left);
        // 更新最大面积
        maxArea = Math.max(maxArea, currentArea);
        // 移动指向较小值的指针
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    return maxArea;
}

四、滑动窗口算法

4.1 滑动窗口算法的基本概念

滑动窗口算法是一种特殊的双指针算法，它使用两个指针来维护一个窗口，这两个指针都朝同一个方向移动。滑动窗口算法通常用于解决子数组或子字符串的问题，例如寻找最长无重复字符子串、最小覆盖子串等。

滑动窗口算法的基本思想是：通过移动两个指针（left和right）来维护一个窗口，窗口内的元素满足一定的条件。在移动的过程中，我们不断地更新窗口的状态，并记录最优解。

4.2 滑动窗口算法的框架

滑动窗口算法的基本框架可以用以下伪代码表示：

int left = 0;
for (int right = 0; right < n; right++) {
    // 扩大窗口，将right指向的元素加入窗口
    window.add(nums[right]);
    // 调整窗口的左边界，直到窗口内的元素满足条件
    while (窗口不满足条件) {
        // 缩小窗口，将left指向的元素移出窗口
        window.remove(nums[left]);
        left++;
    }
    // 更新最优解
    update result;
}

在这个框架中：

left：窗口的左边界
right：窗口的右边界
window：窗口内的元素或窗口的状态
窗口不满足条件：根据具体问题的条件来判断
update result：根据具体问题的要求来更新最优解

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

题目描述：给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。

示例：输入：s = “abcabcbb” 输出：3 解释：因为无重复字符的最长子串是 “abc”，所以其长度为 3。

解题思路：我们可以使用滑动窗口算法来解决这个问题。我们使用一个哈希表来记录窗口内每个字符最后出现的位置，使用两个指针left和right来维护一个窗口，窗口内的字符都是不重复的。当right指向的字符在哈希表中已经存在，并且其位置在left的右侧时，我们需要将left移动到该字符的下一个位置，以确保窗口内的字符都是不重复的。

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> charIndexMap = new HashMap<>();
    int maxLength = 0;
    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        // 如果字符c已经在窗口中，并且其位置在left的右侧，将left移动到该字符的下一个位置
        if (charIndexMap.containsKey(c) && charIndexMap.get(c) >= left) {
            left = charIndexMap.get(c) + 1;
        }
        // 更新字符c的位置
        charIndexMap.put(c, right);
        // 更新最大长度
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

4.4 最小覆盖子串（LeetCode 76）

题目描述：给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

示例：输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC” 解释：最小覆盖子串 “BANC” 包含了字符串 t 的所有字符 ‘A’、‘B’、‘C’

解题思路：我们可以使用滑动窗口算法来解决这个问题。我们使用两个哈希表来分别记录t中每个字符出现的次数和窗口内每个字符出现的次数，使用两个指针left和right来维护一个窗口。当窗口内的字符满足t中的所有字符时，我们尝试缩小窗口，以找到最小的子串。

public String minWindow(String s, String t) {
    // 统计t中每个字符出现的次数
    Map<Character, Integer> targetCount = new HashMap<>();
    for (char c : t.toCharArray()) {
        targetCount.put(c, targetCount.getOrDefault(c, 0) + 1);
    }
    // 统计窗口内每个字符出现的次数
    Map<Character, Integer> windowCount = new HashMap<>();
    // 记录当前窗口中满足t中字符的数量
    int valid = 0;
    // 记录最小子串的起始位置和长度
    int start = 0;
    int minLen = Integer.MAX_VALUE;
    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        // 如果字符c在t中出现，更新窗口内该字符的数量
        if (targetCount.containsKey(c)) {
            windowCount.put(c, windowCount.getOrDefault(c, 0) + 1);
            // 如果窗口内该字符的数量等于t中该字符的数量，增加valid
            if (windowCount.get(c).equals(targetCount.get(c))) {
                valid++;
            }
        }
        // 当窗口内的字符满足t中的所有字符时，尝试缩小窗口
        while (valid == targetCount.size()) {
            // 更新最小子串
            if (right - left + 1 < minLen) {
                start = left;
                minLen = right - left + 1;
            }
            // 缩小窗口
            char leftChar = s.charAt(left);
            if (targetCount.containsKey(leftChar)) {
                // 如果窗口内该字符的数量等于t中该字符的数量，减少valid
                if (windowCount.get(leftChar).equals(targetCount.get(leftChar))) {
                    valid--;
                }
                // 更新窗口内该字符的数量
                windowCount.put(leftChar, windowCount.get(leftChar) - 1);
            }
            left++;
        }
    }
    // 如果没有找到最小子串，返回空字符串
    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

4.5 滑动窗口最大值（LeetCode 239）

题目描述：给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

示例：输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释：滑动窗口的位置最大值

[1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

解题思路：我们可以使用滑动窗口算法和单调队列来解决这个问题。我们使用一个双端队列来维护当前窗口中的最大值的索引。队列中的元素按照从大到小的顺序排列，队首元素是当前窗口中的最大值的索引。当我们移动窗口时，我们需要从队列中移除不在窗口内的元素，并将当前元素与队列中的元素进行比较，移除所有小于当前元素的元素，然后将当前元素的索引加入队列的末尾。这样，队列的队首元素始终是当前窗口中的最大值的索引。

public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n == 0 || k == 0) {
        return new int[0];
    }
    // 结果数组的长度为n - k + 1
    int[] result = new int[n - k + 1];
    // 使用双端队列来维护当前窗口中的最大值的索引
    Deque<Integer> deque = new LinkedList<>();
    for (int right = 0; right < n; right++) {
        // 移除不在窗口内的元素（队列头部的元素）
        while (!deque.isEmpty() && deque.peekFirst() < right - k + 1) {
            deque.pollFirst();
        }
        // 移除所有小于当前元素的元素（队列尾部的元素）
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[right]) {
            deque.pollLast();
        }
        // 将当前元素的索引加入队列的末尾
        deque.offerLast(right);
        // 当窗口的大小等于k时，记录当前窗口的最大值
        if (right >= k - 1) {
            result[right - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

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

题目描述：给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字母异位词指字母相同，但排列不同的字符串。

示例：输入: s = “cbaebabacd”, p = “abc” 输出: [0, 6] 解释: 起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。

解题思路：我们可以使用滑动窗口算法来解决这个问题。我们使用两个哈希表来分别记录p中每个字符出现的次数和窗口内每个字符出现的次数，使用两个指针left和right来维护一个大小为p.length()的窗口。当窗口内的字符与p中的字符完全匹配时，我们记录当前窗口的起始索引。

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> result = new ArrayList<>();
    int sLen = s.length();
    int pLen = p.length();
    if (sLen < pLen) {
        return result;
    }
    // 统计p中每个字符出现的次数
    int[] pCount = new int[26];
    for (char c : p.toCharArray()) {
        pCount[c - 'a']++;
    }
    // 统计窗口内每个字符出现的次数
    int[] windowCount = new int[26];
    // 初始化窗口
    for (int i = 0; i < pLen; i++) {
        windowCount[s.charAt(i) - 'a']++;
    }
    // 检查初始窗口是否与p匹配
    if (Arrays.equals(pCount, windowCount)) {
        result.add(0);
    }
    // 滑动窗口
    for (int right = pLen; right < sLen; right++) {
        // 将right指向的字符加入窗口
        windowCount[s.charAt(right) - 'a']++;
        // 将left指向的字符移出窗口
        windowCount[s.charAt(right - pLen) - 'a']--;
        // 检查窗口是否与p匹配
        if (Arrays.equals(pCount, windowCount)) {
            result.add(right - pLen + 1);
        }
    }
    return result;
}

五、双指针与滑动窗口的高级应用

5.1 三数之和（LeetCode 15）

题目描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

示例：输入：nums = [-1, 0, 1, 2, -1, -4] 输出：[[-1, 0, 1], [-1, -1, 2]]

解题思路：我们可以使用排序和双指针来解决这个问题。首先，我们对数组进行排序。然后，我们遍历排序后的数组，对于每个元素，我们使用左右指针来寻找另外两个元素，使得它们的和等于当前元素的相反数。为了避免重复的三元组，我们需要在遍历和移动指针的过程中跳过重复的元素。

public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    if (n < 3) {
        return result;
    }
    // 对数组进行排序
    Arrays.sort(nums);
    // 遍历排序后的数组
    for (int i = 0; i < n - 2; i++) {
        // 跳过重复的元素
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        // 目标和
        int target = -nums[i];
        // 左右指针
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                // 找到一个三元组
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // 跳过重复的元素
                while (left < right && nums[left] == nums[left + 1]) {
                    left++;
                }
                while (left < right && nums[right] == nums[right - 1]) {
                    right--;
                }
                // 移动指针
                left++;
                right--;
            } else if (sum < target) {
                // 如果和小于目标和，将left向右移动一位
                left++;
            } else {
                // 如果和大于目标和，将right向左移动一位
                right--;
            }
        }
    }
    return result;
}

5.2 四数之和（LeetCode 18）

题目描述：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

示例：输入：nums = [1, 0, -1, 0, -2, 2], target = 0 输出：[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

解题思路：我们可以使用排序和双指针来解决这个问题。首先，我们对数组进行排序。然后，我们使用两层循环来遍历排序后的数组，对于每对元素，我们使用左右指针来寻找另外两个元素，使得它们的和等于target减去当前两个元素的和。为了避免重复的四元组，我们需要在遍历和移动指针的过程中跳过重复的元素。

public List<List<Integer>> fourSum(int[] nums, int target) {
    List<List<Integer>> result = new ArrayList<>();
    int n = nums.length;
    if (n < 4) {
        return result;
    }
    // 对数组进行排序
    Arrays.sort(nums);
    // 遍历排序后的数组
    for (int i = 0; i < n - 3; i++) {
        // 跳过重复的元素
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        // 如果前四个元素的和已经大于target，后面的元素的和只会更大，直接返回
        if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) {
            break;
        }
        // 如果当前元素与最后三个元素的和小于target，跳过当前元素
        if (nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) {
            continue;
        }
        for (int j = i + 1; j < n - 2; j++) {
            // 跳过重复的元素
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            // 目标和
            int subTarget = target - nums[i] - nums[j];
            // 左右指针
            int left = j + 1;
            int right = n - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == subTarget) {
                    // 找到一个四元组
                    result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                    // 跳过重复的元素
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    // 移动指针
                    left++;
                    right--;
                } else if (sum < subTarget) {
                    // 如果和小于目标和，将left向右移动一位
                    left++;
                } else {
                    // 如果和大于目标和，将right向左移动一位
                    right--;
                }
            }
        }
    }
    return result;
}

5.3 接雨水（LeetCode 42）

题目描述：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例：输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

解题思路：我们可以使用双指针来解决这个问题。我们使用两个指针left和right分别从数组的两端向中间移动，同时维护两个变量leftMax和rightMax分别表示left指针左侧的最大高度和right指针右侧的最大高度。在移动的过程中，如果leftMax小于rightMax，那么当前位置能接的雨水量取决于leftMax和当前位置的高度差，然后我们移动left指针；否则，当前位置能接的雨水量取决于rightMax和当前位置的高度差，然后我们移动right指针。

public int trap(int[] height) {
    int n = height.length;
    if (n < 3) {
        return 0;
    }
    int left = 0;
    int right = n - 1;
    int leftMax = 0;
    int rightMax = 0;
    int water = 0;
    while (left < right) {
        // 更新leftMax和rightMax
        leftMax = Math.max(leftMax, height[left]);
        rightMax = Math.max(rightMax, height[right]);
        // 如果leftMax小于rightMax，当前位置能接的雨水量取决于leftMax和当前位置的高度差
        if (leftMax < rightMax) {
            water += leftMax - height[left];
            left++;
        } else {
            // 否则，当前位置能接的雨水量取决于rightMax和当前位置的高度差
            water += rightMax - height[right];
            right--;
        }
    }
    return water;
}

5.4 最长回文子串（LeetCode 5）

题目描述：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例：输入：“babad” 输出：“bab” 注意：“aba” 也是一个有效答案。

解题思路：我们可以使用中心扩展法来解决这个问题，这是一种特殊的双指针算法。我们遍历字符串的每个字符，以该字符为中心，向两边扩展，寻找最长的回文子串。需要注意的是，回文串的长度可能是奇数或偶数，所以我们需要分别处理这两种情况。

public String longestPalindrome(String s) {
    if (s == null || s.length() < 1) {
        return "";
    }
    int start = 0;
    int end = 0;
    // 遍历字符串的每个字符
    for (int i = 0; i < s.length(); i++) {
        // 处理回文串长度为奇数的情况
        int len1 = expandAroundCenter(s, i, i);
        // 处理回文串长度为偶数的情况
        int len2 = expandAroundCenter(s, i, i + 1);
        // 取两种情况的最大值
        int len = Math.max(len1, len2);
        // 更新最长回文子串的起始位置和结束位置
        if (len > end - start) {
            start = i - (len - 1) / 2;
            end = i + len / 2;
        }
    }
    // 返回最长回文子串
    return s.substring(start, end + 1);
}

// 中心扩展法
private int expandAroundCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        // 向两边扩展
        left--;
        right++;
    }
    // 返回回文串的长度
    return right - left - 1;
}

六、双指针与滑动窗口的算法技巧总结

6.1 如何选择合适的双指针策略

在实际应用中，我们需要根据问题的特点来选择合适的双指针策略：

链表问题：通常使用快慢指针，快指针每次移动两步，慢指针每次移动一步
有序数组问题：通常使用左右指针，一个指针从数组的左端开始，另一个指针从数组的右端开始，向中间移动
子数组或子字符串问题：通常使用滑动窗口，两个指针都朝同一个方向移动，形成一个窗口
回文串问题：通常使用中心扩展法，从中心向两边扩展

6.2 常见的优化技巧

剪枝：在遍历的过程中，提前判断某些情况，避免不必要的计算
排序：对于某些问题，先对数组进行排序可以简化问题的解决
哈希表：使用哈希表来记录某些信息，如字符出现的位置、字符出现的次数等
单调队列：使用单调队列来维护窗口中的最大值或最小值

6.3 常见的错误和陷阱

越界问题：在移动指针的过程中，需要注意数组或链表的边界条件，避免越界访问
重复计算问题：在使用滑动窗口时，需要注意窗口的扩大和缩小，避免重复计算
重复解问题：在解决组合问题时，需要注意跳过重复的元素，避免生成重复的解
时间复杂度分析错误：双指针算法的时间复杂度通常是O(n)，但在某些情况下，可能会退化为O(n²)

七、总结与展望

双指针与滑动窗口算法是解决数组和链表问题的重要方法，它们通常可以将时间复杂度从O(n²)降低到O(n)，空间复杂度从O(n)降低到O(1)。在本文中，我们介绍了双指针算法的基本概念、分类和应用场景，并通过具体的LeetCode题目详细讲解了双指针与滑动窗口算法的实现方法和技巧。

双指针算法主要包括同向双指针（快慢指针、滑动窗口）和反向双指针（左右指针）。快慢指针主要用于解决链表问题，如判断链表是否有环、寻找链表的中点等；滑动窗口主要用于解决子数组或子字符串问题，如寻找最长无重复字符子串、最小覆盖子串等；左右指针主要用于解决有序数组问题，如两数之和、三数之和等。

在实际应用中，我们需要根据问题的特点来选择合适的双指针策略，并通过剪枝、排序、哈希表、单调队列等优化技巧来提高算法的效率。同时，我们也需要注意避免越界、重复计算、重复解等常见的错误和陷阱。

随着计算机科学的发展，双指针与滑动窗口算法也在不断地演进和优化。例如，在大数据领域，双指针与滑动窗口算法与并行计算、分布式计算等技术相结合，以应对大规模数据的挑战。此外，双指针与滑动窗口算法也被广泛应用于机器学习、数据挖掘等领域。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-11-12，如有侵权请联系 cloudcommunity@tencent.com 删除

算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度