两道经典算法吃透双指针与滑动窗口！接雨水 + 无重复最长子串超详细题解

在算法面试与刷题中双指针、滑动窗口是高频核心考点既能解决数组区间问题也能高效处理字符串匹配场景。本文将精讲两道力扣经典题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) { // 记录字符及其最近一次出现的下标 HashMapCharacter, 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; } }总结接雨水通过预处理左右最大高度避免重复遍历以空间换时间高效计算总雨水量无重复最长子串滑动窗口 哈希表快速去重线性时间复杂度解决字符串区间问题