力扣高频经典双题解：接雨水 + 无重复最长子串（思路 + 满分代码）

接雨水、无重复字符最长子串是面试高频、算法入门必刷的经典题一道考动态规划预处理一道考滑动窗口都是数组 / 字符串题型里的核心套路。本篇把两道题的思路讲透、代码写清新手也能一遍看懂刷题效率直接拉满42. 接雨水题目描述给定n个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。解题思路核心公式非常直观当前列能接的雨水量 min (左侧最高柱子右侧最高柱子) - 当前柱子高度如果直接对每个柱子都向左右遍历找最大值会产生大量重复计算时间复杂度来到 O (n²)。优化思路很简单提前预处理出左右两侧的最大高度数组用空间换时间把复杂度降到 O (n)。从左向右遍历记录每个位置左边最高柱子高度到leftMax数组从右向左遍历记录每个位置右边最高柱子高度到rightMax数组遍历每一列按公式累加雨水量即可满分代码java运行class Solution { public int trap(int[] height) { int length height.length; // 柱子数≤2无法接水 if (length 2) { return 0; } int[] leftMax new int[length]; int[] rightMax new int[length]; // 左到右记录每个位置左侧最大高度 leftMax[0] height[0]; for (int i 1; i length; i) { leftMax[i] Math.max(height[i], leftMax[i - 1]); } // 右到左记录每个位置右侧最大高度 rightMax[length - 1] height[length - 1]; for (int j length - 2; j 0; j--) { rightMax[j] Math.max(height[j], rightMax[j 1]); } // 累加每一列能接的雨水 int sum 0; for (int i 0; i length; i) { sum Math.min(leftMax[i], rightMax[i]) - height[i]; } return sum; } }3. 无重复字符的最长子串题目描述给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。解题思路这道题是滑动窗口的经典入门题把窗口想象成一段[left, right]区间始终保证区间内无重复字符用left、right双指针表示窗口左右边界初始都为 0right向右扩展尝试把新字符加入窗口如果字符重复且重复位置在窗口内就把left右移收缩窗口每次窗口合法时更新最长子串长度用哈希表记录字符最后一次出现的索引避免重复遍历优化效率满分代码java运行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; } }刷题小结接雨水动态规划预处理左右最大值公式清晰是数组类 “先预处理再计算” 的典型模板无重复最长子串滑动窗口 哈希表去重是字符串高频题型学会窗口思想同类题一通百通