两道经典算法吃透双指针与滑动窗口！接雨水 + 无重复最长子串超详细题解
在算法面试与刷题中，双指针、滑动窗口是高频核心考点，既能解决数组区间问题，也能高效处理字符串匹配场景。本文将精讲两道力扣经典题：42. 接雨水（双指针预处理优化）、3. 无重复字符的最长子串（滑动窗口经典应用），从思路推导到代码实现，带你彻底吃透这类题型。
一、42. 接雨水
题目链接
42. 接雨水 - 力扣（LeetCode）
核心思路
每一列能接到的雨水量，由左侧最高柱子与右侧最高柱子中较小的那个决定：
当前列雨水量 = min (左侧柱子最大高度，右侧柱子最大高度) - 当前柱子高度
如果直接对每个位置分别向左右遍历找最大值，会存在大量重复计算，时间复杂度极高。因此我们采用预处理数组优化：
- 正向遍历，用数组
maxLeft记录每个位置左侧最高柱子高度 - 反向遍历，用数组
maxRight记录每个位置右侧最高柱子高度 - 最后遍历一次数组，累加每一列的接水量即可
递推公式
- 从左到右：
maxLeft[i] = max(height[i], maxLeft[i - 1]) - 从右到左：
maxRight[i] = max(height[i], maxRight[i + 1])
代码实现
class Solution { public int trap(int[] height) { int length = height.length; // 柱子数≤2无法接水 if (length <= 2) { return 0; } int[] maxLeft = new int[length]; int[] maxRight = new int[length]; // 预处理左侧最大高度数组 maxLeft[0] = height[0]; for (int i = 1; i < length; i++) { maxLeft[i] = Math.max(height[i], maxLeft[i - 1]); } // 预处理右侧最大高度数组 maxRight[length - 1] = height[length - 1]; for (int j = length - 2; j >= 0; j--) { maxRight[j] = Math.max(height[j], maxRight[j + 1]); } // 计算总接水量 int sum = 0; for (int i = 0; i < length; i++) { int count = Math.min(maxLeft[i], maxRight[i]) - height[i]; sum += count; } return sum; } }二、3. 无重复字符的最长子串
题目链接
3. 无重复字符的最长子串 - 力扣（LeetCode）
核心思路
本题是滑动窗口的典型例题：把窗口看作字符串中一段无重复字符的区间[left, right]。
right指针向右扩展，尝试将新字符加入窗口- 若当前字符已在窗口内重复，将
left右移，收缩窗口直至无重复 - 每次窗口合法时，更新最长子串长度
使用哈希表记录字符最近一次出现的索引，可快速判断重复并定位窗口左边界。
代码实现
class Solution { public int lengthOfLongestSubstring(String s) { // 记录字符及其最近一次出现的下标 HashMap<Character, Integer> map = new HashMap<>(); int left = 0; int maxLength = 0; for (int right = 0; right < s.length(); right++) { char c = s.charAt(right); // 字符重复且在当前窗口内，移动左边界 if (map.containsKey(c) && map.get(c) >= left) { left = map.get(c) + 1; } // 更新当前字符最新位置 map.put(c, right); // 更新最大长度 maxLength = Math.max(maxLength, right - left + 1); } return maxLength; } }总结
- 接雨水：通过预处理左右最大高度，避免重复遍历，以空间换时间，高效计算总雨水量
- 无重复最长子串：滑动窗口 + 哈希表快速去重，线性时间复杂度解决字符串区间问题