滑动窗口、哈希表、链表

一、滑动窗口模板问题类型典型题干关键词固定长度例题1. 最长/最短子数组满足某条件“最长”“最短”“连续”可变最长无重复子串、最短覆盖子串2. 固定长度子数组统计“长度为 k 的连续”固定长度为 k 的最大平均值、固定大小子数组的最大和3. 计数/是否存在满足条件的子数组“是否存在”“共有多少个”均可和等于目标值的子数组个数4. 两个子数组/字符串比较“两个”“相等”均可找到字符串中所有字母异位词模板求满足条件的最短/最长/计数子数组子串 数组正数、负数、零都通用按需改 while 条件即可 public int slideWindow(int[] nums, int k) { int left 0, ans 0; // 1. 答案变量按需改 int sum 0; // 2. 维护窗口指标和、计数、哈希表… for (int right 0; right nums.length; right) { sum nums[right]; // 3. 右边界右移扩大窗口 while (left right 满足收缩条件) { // 4. 需要收缩就循环 更新答案; // 5. 在收缩前更新最短/计数等 sum - nums[left]; // 6. 去掉头元素 left; // 7. 左边界右移窗口缩小 } 更新答案; // 8. 也可以在扩张后更新最长/计数等 } return ans; }二、哈希表HashSetInteger set new HashSet();场景关键词例题快速查找是否存在、下标、次数两数之和、LRU、字母异位词去重重复、唯一最长无重复子串计数出现次数、频率前 K 个高频元素映射键值对应罗马数字转整数import java.util.HashSet; import java.util.Set; public class TwoSum { 判断数组中是否存在两个元素使得它们的和等于 target param nums 输入数组 param target 目标和 return true 表示存在这样两个元素false 表示不存在 public static boolean hasTwoSum(int[] nums, int target) { //创建一个哈希集合用来存放“已经遍历过的数字”HashSet 基于哈希表实现 SetInteger seen new HashSet(); // 2. 从头到尾扫描数组 for (int num : nums) { // 3. 计算当前数字 num 所需要的“另一半” int complement target - num; // 4. 在常数时间内查哈希表另一半是否出现过 if (seen.contains(complement)) { // 5. 出现过说明 num complement target任务完成 return true; } // 6. 否则把当前数字加入哈希表供后面的数字使用 seen.add(num); } // 7. 扫完整个数组都没找到返回 false return false; } // 简单测试 public static void main(String[] args) { int[] nums {2, 7, 11, 15}; int target 9; System.out.println(hasTwoSum(nums, target)); // 输出 true因为 279 } }三、判断字母出现的次数String s HelloWorld.toLowerCase(); int[] freq new int[26]; // 0 对应 a25 对应 z for (char c : s.toCharArray()) { if (c a c z) { // 过滤非字母 freq[c - a]; } } // 打印示例 for (int i 0; i 26; i) { if (freq[i] 0) System.out.println((char) (i a) : freq[i]); }判断两字符串每个字母出现次数是否相同public static boolean sameLetterCount(String s1, String s2) { int[] cnt1 countLetters(s1); int[] cnt2 countLetters(s2); return Arrays.equals(cnt1, cnt2); // Java 内置数组比较 } private static int[] countLetters(String s) { int[] freq new int[26]; for (char c : s.toLowerCase().toCharArray()) { if (c a c z) { // 忽略非字母 freq[c - a]; } } return freq; }四、判断重复元素HashSetInteger set new HashSet()HashSetInteger set new HashSet(); 这段代码创建了一个用于存储整数的集合这个集合会自动去除重复的元素。它主要用在以下几种常见的场景1. 需要去除重复元素时 当你从某个数据源如数组、列表等读取数据但不希望其中有重复的元素时可以使用 HashSetset.add(number);2. 需要快速判断某个元素是否已存在时set.add(i);3. 实现一些算法问题时 例如在“快乐数”问题中用来记录已经计算过的数字以检测是否存在循环set.add(n);4. 实现简单的缓存功能时当你需要一个简单的缓存来存储最近访问过的元素并且希望快速判断某个元素是否已经在缓存中时set.add(someValue);判断元素是否在缓存中5. 实现集合运算时set1.retainAll(set2);6.!set.add(nums[i]) 如果nums[i]已经在集合中则返回 true表示数组中存在重复元素。五、二维数组1.排序// 1. 按起点升序 Arrays.sort(intervals, (a, b) - a[0] - b[0]); //示例 int[][] intervals {{5,10}, {1,3}, {2,6}}; Arrays.sort(intervals, (a, b) - a[0] - b[0]); 结果[[1,3], [2,6], [5,10]]2.二维数组 ↔ List 互转// 数组 → List Listint[] list Arrays.asList(a); // 注意大小固定不能增删 // 数组 → 可变 List Listint[] list2 new ArrayList(Arrays.asList(a)); // List → 数组 int[][] arr list.toArray(new int[0][]);3.合并重叠区间Arrays.sort(a, (x,y)-Integer.compare(x[0],y[0])); Listint[] m new ArrayList(); for (int[] p : a) { if (m.isEmpty() || m.get(m.size()-1)[1] p[0]) m.add(p); else m.get(m.size()-1)[1] Math.max(m.get(m.size()-1)[1], p[1]); } int[][] merged m.toArray(int[][]::new);4.插入区间阶段区间特征动作① 左边intervals[i].end newInterval.start旧区间的尾和新区间插入的头完全在左侧无交集直接丢进答案② 中间有交集start ≤ newInterval.end end ≥ newInterval.start不断合并把 newInterval 扩成 [min(start)③ 右边intervals[i].start newInterval.end旧区间的头和新插入区间的尾完全在右侧无交集直接丢进答案public int[][] insert(int[][] intervals, int[] newInterval) { Listint[] res new ArrayList(); int i 0, n intervals.length; // 阶段①左边无交集 while (i n intervals[i][1] newInterval[0]) { res.add(intervals[i]); } // 阶段②中间有交集不断合并 while (i n intervals[i][0] newInterval[1]) { newInterval[0] Math.min(newInterval[0], intervals[i][0]); newInterval[1] Math.max(newInterval[1], intervals[i][1]); i; } res.add(newInterval); // 合并后的唯一区间 // 阶段③右边无交集 while (i n) { res.add(intervals[i]); } return res.toArray(new int[res.size()][]); }六、栈StackCharacter stack new Stack();场景关键词例题括号/标签匹配最近匹配、成对出现有效的括号、HTML 标签表达式求值后缀/中缀、运算符优先级基本计算器DFS 非递归回溯、路径二叉树中序遍历非递归单调性维护下一个更大元素、温度每日温度、接雨水中文术语等价代码返回值说明压栈入栈stack.push(E) 或 stack.addLast(E)void把元素放到栈顶弹栈出栈stack.pop() 或 stack.removeLast()E移除并返回栈顶空时抛 NoSuchElementException只看栈顶stack.peek() 或 stack.peekLast()E不删除空时返回 null判空stack.isEmpty()boolean空返回 true获取大小stack.size()int当前元素个数清空stack.clear()void一键变空栈是否包含stack.contains(o)boolean从栈顶到栈底顺序找迭代for (E e : stack)—从栈底→栈顶顺序七、链表1.链表的遍历for (Node p head; p ! null; p p.next) { // 每次循环里 p 指向当前节点 }2.链表的常用方法操作代码示例说明遍历for (Node p head; p ! null; p p.next)从头扫到尾新建节点Node node new ListNode(val);生成新节点后插node.next nextNode;把当前节点指向下一节点随机指针node.random randomNode;随机链表独有头插法node.next head; head node;新节点变新头计数int cnt 0;for (Node p head; p ! null; p p.next) cnt;统计节点个数反转三指针迭代 / 递归经典高频题合并有序双指针归并见前面“合并两条有序链表”✅Map 的常用方法复制随机链表时用MapNode, Node map new HashMap();方法代码示例作用put(K key, V value)map.put(oldNode, newNode);存键值对get(Object key)Node n map.get(oldNode);根据键拿值containsKey(Object key)if (map.containsKey(node))判断键是否存在remove(Object key)map.remove(node);删除键值对clear()map.clear();清空表map使用场景场景关键词示例题目Map 用法随机指针深拷贝复制带随机指针链表原节点 → 新节点快速查找/判重两数之和、最长无重复子串值 → 下标计数/频率前 K 个高频元素、字母异位词分组元素 → 出现次数映射关系罗马数字转整数、13 号罗马罗马字符 → 数值分组按出现次数排序、字母异位词key 设计为“签名”缓存/记忆化递归加缓存DP 备忘录参数 → 计算结果✅ 反面教材别滥用只是顺序遍历 → 用 List/数组只要两头操作 → 用 Deque只要排序 → 用 TreeSet/优先队列八、树和二叉树1.二叉树的翻转递归实现 class TreeNode { int val;//给每个节点存一个整数值 TreeNode left, right; TreeNode(int x) { val x; }//新建节点时一次性把值填进去。 } public class Solution { // 主接口 public TreeNode invertTree(TreeNode root) { if (root null) return null; // 交换左右子树 TreeNode tmp root.left; root.left root.right; root.right tmp; // 递归处理子树 invertTree(root.left); invertTree(root.right); return root; } }2.获取节点值System.arraycopy 把一段数组里的元素快速拷贝到另一段数组里System.arraycopy(源数组, 源起始下标, 目标数组, 目标起始下标, 复制长度);// 4. 新建 4 个小数组左前序、左中序、右前序、右中序 int[] leftPre new int[leftSize];//左子树的前序 int[] leftIn new int[leftSize];//左子树的中序 int[] rightPre new int[rightSize];//右子树的前序 int[] rightIn new int[rightSize];//右子树的中序 //开始拿数据 //从第 1 个开始拿leftSize个 → 就是左子树的前序。 System.arraycopy(preorder, 1, leftPre, 0, leftSize); //中序里根左边正好leftSize个元素 → 左子树的中序。 System.arraycopy(inorder, 0, leftIn, 0, leftSize); //前序里根后面先走左子树再走右子树所以右子树从1 leftSize开始拿。 System.arraycopy(preorder, 1 leftSize, rightPre, 0, rightSize); //中序里根右边所有元素 → 右子树的中序 System.arraycopy(inorder, rootPos 1, rightIn, 0, rightSize);3.前序和中序构建二叉树//前序负责找根中序负责分左右。中序遍历根的下标值就是左子树个数。 class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { // 边界 if (preorder.length 0) return null; // 1. 前序第 0 个就是根 int rootVal preorder[0]; TreeNode root new TreeNode(rootVal); // 2. 在中序里找根的位置 int rootPos 0; for (int i 0; i inorder.length; i) { if (inorder[i] rootVal) { rootPos i;//记录下根节点的值的下标 break; } } // 3. 切成左、右两份 int leftSize rootPos; // 左子树节点个数中序遍历根的下标值就是左子树个数 int rightSize inorder.length - leftSize - 1; // 4. 新建 4 个小数组左前序、左中序、右前序、右中序 int[] leftPre new int[leftSize];//左子树的前序 int[] leftIn new int[leftSize];//左子树的中序 int[] rightPre new int[rightSize];//右子树的前序 int[] rightIn new int[rightSize];//右子树的中序 //开始拿数据 System.arraycopy(preorder, 1, leftPre, 0, leftSize); System.arraycopy(inorder, 0, leftIn, 0, leftSize); System.arraycopy(preorder, 1 leftSize, rightPre, 0, rightSize); System.arraycopy(inorder, rootPos 1, rightIn, 0, rightSize); // 5. 递归搭左、右子树 root.left buildTree(leftPre, leftIn); root.right buildTree(rightPre, rightIn); return root; } }4.中序和后序构建二叉树后序找根中序分左右1. 后序最后一个元素就是根2. 去中序里找到这个根左边全是左子树右边全是右子树3. 根据左子树长度把后序也切成左、右两份4. 对左右两份重复 1→2→3直到分空/*后序找根中序分左右 */ class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { //用递归函数处理整棵树的区间 return build(inorder, 0, inorder.length - 1,//中序从 0 号到末尾 postorder, 0, postorder.length - 1);//后序从 0 号到末尾 } // il..ir 中序区间pl..pr 后序区间 //in是原始中序数组post是原始后序数组 private TreeNode build(int[] in, int il, int ir, int[] post, int pl, int pr) { if (il ir) return null; int rootVal post[pr]; //后序最后一个就是根 TreeNode root new TreeNode(rootVal); // 在中序里找根 int rootPos il; while (in[rootPos] ! rootVal) rootPos; int leftSize rootPos - il; //左子树节点个数 root.left build(in, il, rootPos - 1, post, pl, pl leftSize - 1); root.right build(in, rootPos 1, ir, post, pl leftSize, pr - 1); return root; } }5.获取完全二叉树的节点个数class Solution { public int countNodes(TreeNode root) { if(root null){ return 0; } int left countLevel(root.left); int right countLevel(root.right); if(left right){ return countNodes(root.right) (1left); }else{ return countNodes(root.left) (1right); } } private int countLevel(TreeNode root){ int level 0; while(root ! null){ level; root root.left; } return level; } }