国家免费培训网站,html5的网站有哪些,wordpress 页面 固定链接,创建5a 网站建设要求引言#xff1a;算法选择的十字路口 在算法面试中#xff0c;双指针和滑动窗口如同两把瑞士军刀#xff0c;能高效解决80%以上的数组和字符串问题。本文将深入解析这两种技术的核心差异#xff0c;结合力扣高频题目#xff0c;提供可直接复用的代码。 一、算法核心思想解析… 引言算法选择的十字路口 在算法面试中双指针和滑动窗口如同两把瑞士军刀能高效解决80%以上的数组和字符串问题。本文将深入解析这两种技术的核心差异结合力扣高频题目提供可直接复用的代码。 一、算法核心思想解析 1. 双指针技术 双指针算法是通过维护两个指针变量通常为数组/链表索引协同遍历数据结构的高效策略主要用于优化暴力解法的时空复杂度。 三种经典模式 对撞指针首尾指针向中间收敛如三数之和快慢指针同向移动但速度不同如环形链表检测滑动窗口动态维护子区间特殊双指针实现 2. 滑动窗口技术 作为双指针的特殊形式滑动窗口具有以下特点 两个指针同向移动且维护一个连续区间通过窗口扩张/收缩动态调整解空间 3. 算法特性对比 特性 双指针算法 滑动窗口算法 指针移动方向 可对撞/同向 严格同向移动 数据要求 常需排序 原始数据即可 时间复杂度 O(n)~O(n²) O(n) 典型问题 有序数组组合问题 子串/子数组最优解 状态维护 通常不需要 需要哈希表记录状态 二、高频面试题分类精讲 1. 双指针经典题型三数之和LeetCode 15 解题思路 1. 暴力解法不推荐 最直观的方法是三重循环遍历所有可能的三元组时间复杂度为O(n³)效率太低。 2. 排序 双指针法推荐 步骤如下 排序数组首先将数组排序这样可以利用有序性来优化搜索固定一个数遍历数组将当前元素作为第一个数双指针搜索在当前元素后面的部分使用双指针左指针从当前元素后一位开始右指针从数组末尾开始寻找另外两个数去重处理跳过重复的元素以避免重复解 时间复杂度O(n²)排序O(nlogn) 双指针遍历O(n²) public ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();int length nums.length;if (nums null || length 3) {return result;}Arrays.sort(nums); // 关键步骤排序for (int i 0; i length; i) {// 需要和上一次枚举的数不相同if (i 0 nums[i] nums[i - 1]) {continue;}int left i1;int right length - 1;int target -nums[i]; // nums[left] nums[right] targetwhile(left right) {int sum nums[left] nums[right];if (sum target) {result.add(Arrays.asList(nums[i], nums[left], nums[right]));// 跳过重复的left和rightwhile (left right nums[left] nums[left 1]) left;while (left right nums[right] nums[right - 1]) right--;left;right--;} else if (sum target) {left;} else {right--;}}}return result;}2. 滑动窗口经典题型最小覆盖子串LeetCode 76 算法核心思想 滑动窗口Sliding Window算法是解决最小覆盖子串问题的最优方法 双指针定义窗口使用left和right两个指针表示当前考察的子串窗口哈希表记录需求使用两个哈希表分别存储 need目标字符串T中各字符的需求量window当前窗口中满足需求的字符数量 3. 动态扩展收缩窗口 先扩展right指针寻找可行解再收缩left指针优化解 4. 有效字符计数通过valid变量统计窗口中已满足需求的字符种类数 5. 实时更新结果每当找到更小的满足条件的子串时更新结果 复杂度分析 时间复杂度O(n)其中n是字符串S的长度空间复杂度O(m)其中m是字符集大小通常为常数级 Java实现代码 public String minWindow(String s, String t) {// 边界条件检查if (s null || t null || s.length() t.length()) {return ;}// 初始化需求哈希表记录t中每个字符出现的次数MapCharacter, Integer need new HashMap();for (char c : t.toCharArray()) {need.put(c, need.getOrDefault(c, 0) 1);}// 初始化窗口哈希表记录当前窗口中满足需求的字符数量MapCharacter, Integer window new HashMap();// 记录窗口中满足need条件的字符个数int valid 0;// 记录最小覆盖子串的起始位置和长度int start 0, minLen Integer.MAX_VALUE;// 滑动窗口左右指针int left 0, right 0;while (right s.length()) {// 获取右指针当前字符char c s.charAt(right);// 右指针向右移动right;// 如果当前字符在需求表中则更新窗口计数if (need.containsKey(c)) {window.put(c, window.getOrDefault(c, 0) 1);// 如果窗口中该字符数量等于需求数量则valid加1if (window.get(c).equals(need.get(c))) {valid;}}// 当窗口满足所有字符需求时尝试收缩左边界while (valid need.size()) {// 更新最小覆盖子串信息if (right - left minLen) {start left;minLen right - left;}// 获取左指针当前字符char d s.charAt(left);// 左指针向右移动left;// 如果移出的字符在需求表中则更新窗口计数if (need.containsKey(d)) {// 如果窗口中该字符数量刚好等于需求数量则valid减1if (window.get(d).equals(need.get(d))) {valid--;}window.put(d, window.get(d) - 1);}}}// 返回最小覆盖子串如果没有找到则返回空字符串return minLen Integer.MAX_VALUE ? : s.substring(start, start minLen);}三、算法选择的核心判别特征 1. 双指针算法的识别特征 当问题呈现以下至少两个特征时优先考虑双指针算法 线性序列结构数组/链表 典型表现输入数据为数组或链表等线性结构反例树形结构或图结构通常不适用 有序性或可排序性 典型表现题目明确说明已排序或允许预处理排序示例特征非递减顺序排列、你可以假设数组已经按升序排列 对称性/双向操作需求 典型表现需要从两端向中间或特定方向协同操作示例场景回文判断、盛水容器问题 组合优化问题 典型表现需要寻找两个或多个元素的特定组合示例模式找出满足条件的两个元素、确定三个数的组合 2. 滑动窗口算法的识别特征 当问题呈现以下至少两个特征时优先考虑滑动窗口算法 连续子区间要求 典型表现需要处理数组中连续的序列或子串关键词连续子数组、子串、连续的...满足条件 窗口可变或固定大小 典型表现需要动态调整或保持固定大小的区间可变窗口特征最短/最长满足条件的...固定窗口特征大小为k的... 统计类约束条件 典型表现基于频率、和、平均值等统计量的条件判断示例条件包含所有字符、和≥target、无重复字符 最优解搜索 典型表现需要寻找满足特定条件的最优区间典型目标最小的...满足...、最大的...满足... 3. 特征验证案例 案例1三数之和双指针 ✅ 线性结构数组✅ 可排序性题目允许排序✅ 组合问题找三个数✅ 对称操作需要跳过重复解 案例2最小覆盖子串滑动窗口 ✅ 连续子区间子串要求连续✅ 可变窗口找最短满足条件的✅ 统计条件包含所有字符✅ 最优解搜索最小窗口 4. 应用场景选择指南 1. 优先选择双指针的情况 有序数组的组合问题如两数之和、三数之和链表操作如环形链表检测、链表中点定位对称性问题如回文串验证、反转字符串 2. 优先选择滑动窗口的情况 连续子序列问题如最小覆盖子串、最长无重复子串区间统计问题如和大于等于目标值的最短子数组固定窗口大小问题如大小为k的子数组的最大平均值 四、力扣经典案例 4.1、基础双指针问题 4.1.1. 对撞指针经典题 167. 两数之和 II - 输入有序数组 解法特点有序数组相向指针遍历时间复杂度O(n) 344. 反转字符串 解法特点原地操作字符数组空间复杂度O(1) 4.2、滑动窗口常规问题 4.2.1. 可变窗口基础题 209. 长度最小的子数组 解法特点动态调整窗口大小关键点维护窗口和与目标值的比较 4.2.2. 哈希表辅助窗口题 3. 无重复字符的最长子串 解法特点哈希表记录字符最后出现位置时间复杂度O(n) 4.3、字符串匹配问题 4.3.1. 困难级窗口问题 76. 最小覆盖子串 解法特点精确的窗口收缩条件关键点有效字符计数机制 4.3.2. 固定窗口典型题 438. 找到字符串中所有字母异位词 解法特点固定长度窗口滑动优化点数组替代哈希表统计字符 4.4、链表双指针问题 4.4.1. 快慢指针经典题 141. 环形链表 解法特点Floyd判圈算法空间复杂度O(1) 4.4.2. 前后指针应用 19. 删除链表的倒数第 N 个结点 解法特点前后指针保持固定间距关键点虚拟头节点处理边界 4.5、多维滑动窗口问题 4.5.1. 单调队列配合题 239. 滑动窗口最大值 解法特点单调递减队列维护窗口极值时间复杂度O(n) 4.5.2. 双堆进阶问题 480. 滑动窗口中位数 解法特点大小顶堆平衡维护中位数关键点延迟删除策略 结语算法精进的阶梯 掌握双指针和滑动窗口不仅是面试的敲门砖更是提升算法思维的关键。建议读者按照解题模板→理解原理→独立实现→优化变体的路径系统学习逐步构建自己的算法兵器库。 附高频核心算法 动态规划(DP)从核心场景识别到优化技巧 堆排序原理、实现与优化
