Hot100（开刷） 之 长度最小的数组--删除倒数第N个链表--层序遍历

27.长度最小的数组解题方式这段代码利用滑动窗口通过右指针不断扩展窗口累加元素并在和满足条件时移动左指针收缩窗口从而在 O(n)O(n) 时间内找到满足和 ≥≥ 目标值的最小长度子数组。public int minSubArrayLen(int target, int[] nums) { int l nums.length; int sum 0,left0; int res Integer.MAX_VALUE; for(int right 0 ;rightl ;right){ sumnums[right]; while(sumtarget){ res Math.min(res,right-left1); sum-nums[left]; left; } } return res Integer.MAX_VALUE?0:res; }//数组长度 val len nums.size //最大值 var res Int.MAX_VALUE //最大值最小值 maxOf/ minOf() fun minSubArrayLen(target: Int, nums: IntArray): Int { val len nums.size var sum 0 var left 0 var res Int.MAX_VALUE for (right in 0 until len) { // 将右边界元素加入窗口 sum nums[right] // 当窗口和满足条件时尝试收缩左边界 while (sum target) { // 更新最小长度 res minOf(res, right - left 1) // 移除左边界元素并移动左指针 sum - nums[left] left } } // 如果 res 未被更新过说明没有找到满足条件的子数组返回 0 return if (res Int.MAX_VALUE) 0 else res } }1.代码逻辑详解这段代码利用滑动窗口的思想在一次遍历中寻找满足条件的最小子数组长度。初始化阶段sum 0用于记录当前滑动窗口内元素的总和。left 0滑动窗口的左边界起始位置。res Integer.MAX_VALUE用于记录满足条件的最小长度。初始化为最大值是为了方便后续进行比较取最小值如果最后这个值没变说明没找到符合条件的子数组。扩展窗口移动右指针right通过for循环遍历数组right指针充当窗口的右边界。sum nums[right]将当前右边界指向的元素加入窗口更新当前窗口的总和。收缩窗口移动左指针leftwhile (sum target)这是一个核心判断。只要当前窗口内的元素和sum大于或等于目标值target说明我们找到了一个合法的子数组。更新结果在while循环内部首先计算当前窗口的长度right - left 1并与历史最小值res比较保留较小的那个。尝试更优解为了寻找可能更短的子数组我们需要缩小窗口。sum - nums[left]将左边界元素从总和中减去。left左边界向右移动一位。这个过程会一直持续直到窗口内的和小于target为止。返回结果最后判断res是否仍为Integer.MAX_VALUE。如果是说明从未进入过while循环即没有任何子数组和满足条件返回0否则返回记录的最小长度res。2. 关键点窗口收缩的条件必须是while (sum target)。这里不能写成if因为当找到一个满足条件的窗口后可能需要连续移动多次left才能让sum再次小于target。例如如果数组元素很小而target很大可能移动一次不够或者当前窗口非常大移动一次后可能仍然满足条件我们需要一直移动到刚好不满足为止以确保找到以当前right结尾的最短子数组。长度的计算数组下标是从 0 开始的所以从left到right的长度是right - left 1。哨兵值的使用使用Integer.MAX_VALUE作为初始值是一个常用的技巧用来标记“尚未找到解”的状态。3. 复杂度分析时间复杂度O(N)其中 NN是数组的长度。虽然代码中有两层循环for和while但这并不是 O(N2)O(N2) 。因为每个元素最多被访问两次一次是被右指针right加入窗口另一次是被左指针left移出窗口。因此操作总次数是线性的即 2N2N简化为 O(N)O(N) 。空间复杂度O(1)只需要常数级别的额外空间来存储变量sum、left、right和res不需要依赖输入数组大小的额外存储空间。4. 优缺点优点高效相比于暴力解法双重循环枚举所有子数组时间复杂度 O(N2)O(N2) 滑动窗口将时间复杂度降低到了 O(N)O(N) 在处理大规模数据时性能优势非常明显。逻辑清晰代码结构简洁通过维护两个指针即可动态调整窗口大小易于理解和实现。缺点适用场景受限这种“快慢指针”式的滑动窗口主要适用于数组元素均为正整数的情况。局限性说明如果数组中包含负数sum随着right的增加不一定增加随着left的增加不一定减少此时while (sum target)的逻辑就会失效因为缩小窗口可能会导致和变大或者扩大窗口导致和变小这种算法就不再适用了。28.删除倒数第N个链表代码通过引入哑结点简化边界处理先遍历链表计算总长度再根据长度定位到待删除节点的前驱最后修改指针指向完成删除。public ListNode removeNthFromEnd(ListNode head, int n) { //建立含头节点的节点防止删除头节点无法操作 ListNode dummy new ListNode(0, head); int length getLength(head); ListNode cur dummy; for (int i 1; i length - n 1; i) { cur cur.next; } cur.next cur.next.next; ListNode ans dummy.next; return ans; } public int getLength(ListNode head) { int length 0; while (head ! null) { length; head head.next; } return length; } }1.代码逻辑详解这段代码的核心思路非常直观要删除倒数第 NN个节点首先需要知道链表的总长度从而算出该节点在正数第几个位置。引入哑结点创建一个哑结点dummy其next指向head。目的处理边界情况。如果链表只有一个节点且需要删除它或者需要删除头结点直接操作head会非常麻烦。使用dummy可以让我们统一处理所有节点的删除逻辑最后返回dummy.next即可。第一次遍历计算长度调用getLength(head)方法。该方法通过while循环遍历整个链表统计节点总数length。定位待删除节点的前驱我们需要删除的是倒数第 NN个节点。假设链表长度为 LL那么倒数第 NN个节点就是正数第 L−N1L−N1 个节点。为了执行删除操作cur.next cur.next.next我们需要找到待删除节点的前一个节点即第 L−NL−N个节点。代码中cur初始化为dummy相当于第 0 个节点。for循环从i 1执行到i length - n 1。这意味着循环体执行了 L−NL−N次cur指针最终停留在第 L−NL−N个节点上。执行删除cur.next cur.next.next跳过待删除的节点将其前驱直接连接到其后继。返回结果返回dummy.next即处理后的新链表头结点。2. 关键点哑结点Dummy Node这是链表题目中的经典技巧。它避免了在删除头结点时需要单独判断head null或返回head.next的复杂逻辑使代码更加健壮。索引计算链表长度 LL目标节点位置从1开始 L−N1L−N1目标前驱节点位置从0开始dummy为0 L−NL−N循环条件i length - n 1实际上就是让cur走 L−NL−N步正好停在待删除节点的前一位。边界情况例如链表长度为 5删除倒数第 1 个即正数第 5 个。cur需要走到第 4 个节点。公式 5−145−14 逻辑成立。3. 复杂度分析时间复杂度O(L)其中 LL是链表的长度。getLength方法遍历了一次链表耗时 O(L)O(L) 。主函数中的for循环遍历了部分链表从头到待删除节点前耗时 O(L)O(L) 。总时间复杂度为 O(L)O(L)O(L)O(L)O(L)O(L) 。空间复杂度O(1)只需要常数级别的额外空间来存储dummy、cur、length等变量不依赖链表长度。4. 优缺点优点逻辑简单符合直觉先算总数再找位置容易理解和编写不易出错。代码清晰将“计算长度”封装成独立函数主逻辑非常干净。缺点遍历次数需要遍历链表两次一次算长度一次找位置。虽然时间复杂度量级相同但在实际运行中比“一次遍历”的方法如双指针/快慢指针法稍慢。改进空间可以使用快慢指针技巧。让快指针先走 NN步然后快慢指针同时移动当快指针到达末尾时慢指针正好指向待删除节点的前驱。这样只需要一次遍历。29.层序遍历解题方式利用队列实现广度优先搜索通过记录每一层的节点数量来分层处理依次将节点出队取值并将其子节点入队从而完成二叉树的层序遍历。//offeer 加到末尾 //poll 删除并返回第一个元素 public ListListInteger levelOrder(TreeNode root) { // 结果列表每个元素是一个 ListInteger代表一层的节点值 ListListInteger res new ArrayList(); // 如果根节点为空直接返回空结果 if (root null) return res; // 使用 LinkedList 作为队列实现广度优先搜索BFS // offer() 方法在尾部添加元素poll() 方法从头部取出并删除元素 LinkedListTreeNode queue new LinkedList(); queue.offer(root); // 先将根节点入队 // 当队列不为空时说明还有节点未处理 while (!queue.isEmpty()) { // 临时列表用于存储当前层的所有节点值 ListInteger levelValues new ArrayList(); // 当前队列的大小就是当前层的节点个数因为上一层节点已经全部出队 int size queue.size(); // 循环处理当前层的每一个节点 while (size ! 0) { // 弹出队首节点当前层的节点 TreeNode currentNode queue.poll(); // 将当前节点的值加入当前层的列表 levelValues.add(currentNode.val); // 如果左子节点不为空则将其加入队列下一层 if (currentNode.left ! null) queue.offer(currentNode.left); // 如果右子节点不为空则将其加入队列下一层 if (currentNode.right ! null) queue.offer(currentNode.right); // 当前层剩余待处理节点数减1 size--; } // 当前层所有节点处理完毕将这一层的结果加入最终结果列表 res.add(levelValues); } // 返回完整的层序遍历结果 return res; }fun levelOrder(root: TreeNode?): ListListInt { val res ArrayListListInt() // 如果根节点为空直接返回空结果 if (root null) return res // Kotlin 中通常使用 ArrayDeque 来实现队列性能优于 LinkedList val queue: QueueTreeNode ArrayDeque() queue.offer(root) // 当队列不为空时说明还有节点未处理 while (queue.isNotEmpty()) { val levelValues ArrayListInt() // 记录当前层的节点数量 val size queue.size // 循环处理当前层的每一个节点 for (i in 0 until size) { // 弹出队首节点 val currentNode queue.poll() // 将当前节点的值加入当前层的列表 levelValues.add(currentNode.val) // 如果左子节点不为空加入队列 if (currentNode.left ! null) queue.offer(currentNode.left) // 如果右子节点不为空加入队列 if (currentNode.right ! null) queue.offer(currentNode.right) } // 当前层处理完毕加入结果列表 res.add(levelValues) } return res }1. 代码逻辑详解这段代码使用了广度优先搜索的策略借助一个队列来实现二叉树的层序遍历。初始化与边界处理创建一个结果列表res用于存储最终的层序遍历结果。首先判断根节点root是否为空。如果为空直接返回空列表避免空指针异常。队列初始化使用LinkedList创建一个队列queue并将根节点root加入队列offer。队列的作用是暂存当前层以及下一层需要访问的节点遵循“先进先出”的原则。外层循环控制层数while (!queue.isEmpty())只要队列不为空说明树中还有节点未被访问。每次进入外层循环意味着开始处理新的一层。内层循环处理当前层创建一个临时列表levelValues用于存储当前层所有节点的值。关键步骤int size queue.size()。在开始处理当前层之前先记录队列的大小。这个size正好是当前层节点的总数因为上一层的节点已经全部出队而当前层的节点已经全部入队。while (size ! 0)循环size次确保只处理当前层的节点而不混入下一层新加入的节点。queue.poll()取出队首节点即当前层的一个节点。levelValues.add(...)将该节点的值存入临时列表。子节点入队如果当前节点有左子节点或右子节点将它们依次加入队列。注意这些新加入的节点属于下一层它们会在下一次外层循环中被处理。size--当前层待处理节点数减 1。收集结果当内层循环结束时说明当前层的所有节点都已处理完毕。将levelValues当前层的节点值列表加入到最终结果res中。2. 关键点队列的作用队列是 BFS 的核心数据结构。它保证了节点是按照“从上到下、从左到右”的顺序被访问的。“快照”思想size变量这是层序遍历最关键的技巧。因为在内层循环中我们会不断向队列中添加下一层的节点导致队列长度动态变化。如果不先记录size就无法区分哪些节点属于当前层哪些属于下一层。通过固定size我们将每一层的处理过程隔离开来。空树处理代码开头对root null的判断是必不可少的鲁棒性检查。3. 复杂度分析时间复杂度O(N)其中 NN是二叉树的节点总数。每个节点都会被入队一次、出队一次且仅被访问一次。因此总的时间复杂度是线性的。空间复杂度O(W)其中 WW是二叉树的最大宽度即某一层拥有的最大节点数。队列中最多同时存储一层的所有节点。在最坏情况下例如完全二叉树的最后一层空间复杂度为 O(N)O(N) 在最好情况下链状树空间复杂度为 O(1)O(1) 。平均来看空间复杂度取决于树的最大宽度。4. 优缺点优点逻辑清晰利用队列模拟层级扩散的过程非常符合人类对“层”的直观理解。通用性强这是解决二叉树层级相关问题如求平均层值、锯齿形遍历、寻找最底层最左边节点等的标准模板。缺点空间开销相比于深度优先搜索BFS 需要维护一个队列来存储节点。对于宽度非常大的树例如完全二叉树队列可能会占用较多内存。递归替代虽然也可以用深度优先搜索配合记录“当前深度”来通过递归实现层序遍历但那种方法需要额外的逻辑来管理层级索引不如 BFS 直观