LeetCode 算法题解：滑动窗口与数组合并的实战应用-云帆数科

目录题目一3. 无重复字符的最长子串 - 力扣LeetCode题目描述为什么选择“滑动窗口哈希表”解题思路滑动窗口哈希表Java 代码实现题目二4. 寻找两个正序数组的中位数 - 力扣LeetCode题目描述为什么选择“双指针合并法”以及它的局限Java 代码实现双指针合并法题目一3. 无重复字符的最长子串 - 力扣LeetCode题目描述给定一个字符串s请你找出其中不含有重复字符的最长子串的长度。示例 1:输入:s abcabcbb输出:3解释:因为无重复字符的最长子串是abc所以其长度为 3。注意bca和cab也是正确答案。示例 2:输入:s bbbbb输出:1解释:因为无重复字符的最长子串是b所以其长度为 1。示例 3:输入:s pwwkew输出:3解释:因为无重复字符的最长子串是wke所以其长度为 3。为什么选择“滑动窗口哈希表”看到这道题我们的思考路径应该是这样的抓住关键字“子串”。子串意味着必须是连续的一段。这与“子序列”可以不连续有本质区别。对于连续区间的问题最常用的思想就是双指针。抓住关键字“无重复”。既然要求无重复我们就需要一个数据结构通常是哈希表或数组来记录当前区间内出现了哪些字符及其频次以便做到 O(1)O(1) 的快速查询。为什么不用暴力法如果暴力枚举所有子串再用哈希表判断是否重复时间复杂度会达到 O(N2)O(N2) 甚至 O(N3)O(N3)当字符串很长时一定会超时。为什么是“滑动窗口”假设我们已经找到了一个无重复的子串[left, right]。当我们把右边界right往右移动一个字符时如果新字符没出现过那太好了当前无重复子串变长了更新答案。如果新字符出现过说明当前窗口里有重复元素了。关键来了我们不需要把left退回起点重新开始那是暴力法因为既然包含了新字符后发生重复那么只要那个重复的字符还在窗口里子串就一直不合法。因此我们只需要把左边界left不断向右移动直到把那个重复的字符“挤出去”为止。这种left和right都只向右移动、不回退的特性被称为单调性这正是滑动窗口能将时间复杂度降到 O(N)O(N) 的核心原因。解题思路滑动窗口哈希表这道题是经典的滑动窗口Sliding Window应用题。定义两个指针left和right分别代表窗口的左右边界。使用一个HashMap来记录窗口内字符出现的次数。right指针不断向右移动每次移动将当前字符加入HashMap并计数。当HashMap中某个字符的计数大于 1 时说明窗口内出现了重复字符。此时我们需要移动left指针缩小窗口直到该字符的计数重新回到 1。在每次循环中更新当前无重复字符子串的最大长度ret。Java 代码实现class Solution { public int lengthOfLongestSubstring(String s) { char[] str s.toCharArray(); int n str.length; int left 0, right 0, ret 0; // 用于记录窗口内字符出现的频次 MapCharacter, Integer hash new HashMap(); while (right n) { char ch str[right]; hash.put(ch, hash.getOrDefault(ch, 0) 1); // 如果当前字符出现次数大于 1说明窗口内存在重复字符 // 移动左指针缩小窗口直到该字符的频次降为 1 while (hash.get(ch) 1) { hash.put(str[left], hash.get(str[left]) - 1); left; } // 更新最大长度 ret Math.max(ret, right - left 1); right; } return ret; } }题目二4. 寻找两个正序数组的中位数 - 力扣LeetCode题目描述给定两个大小分别为m和n的正序从小到大数组nums1和nums2。请你找出并返回这两个正序数组的中位数。要求算法的时间复杂度应该为 O(log⁡(mn))O(log(mn))。示例 1:输入:nums1 [1,3], nums2 [2]输出:2.00000解释:合并数组 [1,2,3]中位数 2示例 2:输入:nums1 [1,2], nums2 [3,4]输出:2.50000解释:合并数组 [1,2,3,4]中位数 (2 3) / 2 2.5为什么选择“双指针合并法”以及它的局限从这道题的题干中我们可以提取出几个核心线索“两个正序数组”既然是有序的那就极大概率可以用到双指针。这就好比我们有两叠按大小排好的扑克牌要把它们合在一起按顺序排好最直观的方法就是两只手各拿一叠每次比较最上面的一张谁小就先放下。“中位数”中位数的定义是将数组排序后处于中间位置的数。这天然就需要我们对数据进行“排序”或者“找第 K 小”的操作。为什么图片中用了双指针合并因为这是最符合人类直觉的解法。开辟一个新数组用两个指针分别遍历两个原数组每次把较小的元素放入新数组。合并完成后直接根据新数组的总长度的奇偶性取出中位数。这种方法的问题在哪虽然直观易懂但它的时间复杂度是O(mn)O(mn)空间复杂度也是O(mn)O(mn)。注意题目要求时间复杂度应为 O(log⁡(mn))O(log(mn))。看到log这个词我们应该本能地想到“二分查找”。Java 代码实现双指针合并法class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m nums1.length, n nums2.length; int[] arr new int[m n]; int left 0, right 0, i 0; // 1. 双指针合并两个有序数组 while (left m || right n) { // 使用 0x3f3f3f3f 作为无穷大占位符防止数组越界 int s1 0x3f3f3f3f; int s2 0x3f3f3f3f; if (left m) s1 nums1[left]; if (right n) s2 nums2[right]; if (s1 s2) { arr[i] s2; right; } else { arr[i] s1; left; } } int sum m n; if (sum 0) return 0; // 2. 计算中位数 if (sum % 2 0) { // 偶数个元素中间两个数的平均值 return (double)(arr[sum / 2 - 1] arr[sum / 2]) / 2; } else { // 奇数个元素正中间的数 return (double)arr[sum / 2]; } } }

企业数字化 ERP 产品动态

相关推荐

不懂代码，怎么用AI自动处理Excel数据、生成报表？手把手实操指南

适用人群：财务、销售、运营、物流、供应链、银行与人事等需要天天跟表格打交道的办公人；也适合不会写代码、但想把手动整理Excel的时间省下来的你。全文按“准备工作 → 操作步骤 → 注意事项 → 常见问题”四段写，跟着做就能跑通一条“一句话… · 2026/11/2 15:07:32

AI算的财务数据敢直接用吗？六维可信度横评：四种方案的保障机制实测

三方评测视角聚焦「财务数据可信度」这一个问题 2026 年 10 月评测口径：公开文档核对对四类代表性方案做六维可信度保障评测（确定性、落点可控、口径一致性、可复核性、交付可用、成本可预期），满分 5 分。所有分数只代表「让… · 2026/11/1 2:00:35

LangChain4j 生态框架深度横评：深度剖析与LangGraph、 Spring AI 核心差异

在构建复杂的企业级 AI 应用时，我们常常面临一个两难选择：是直接使用大模型原生的 API 进行简单的问答封装，还是投入精力搭建一套能够处理长流程、多状态、高可靠性的智能体系统？很多开发者在初期往往低估了业务逻辑的复杂度&… · 2026/11/1 2:00:35

Kornia 中值模糊（Median Blur）并行化分析与 CPU 快速路径实现详解

计算机视觉深度学习图像处理【免费下载链接】kornia 🐍 Geometric Computer Vision Library for Spatial AI 项目地址： https://gitcode.com/GitHub_Trending/ko/kornia 点击查看免费下载中值模糊是图像去噪中的经典非线性算子，但在深度学… · 2026/11/2 15:04:37

wkhtmltopdf HTML转PDF 实战指南：从 HTML 文件到成品 PDF

wkhtmltopdf HTML转PDF 实战指南：从 HTML 文件到成品 PDF 【免费下载链接】wkhtmltopdf Convert HTML to PDF using Webkit (QtWebKit) 项目地址: https://gitcode.com/gh_mirrors/wk/wkhtmltopdf wkhtmltopdf 是一款基于 QT Webkit 渲染引擎的无头命令行工具… · 2026/11/2 15:03:31

Harmony OS C++实战

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 15:03:31

九联UNT402A刷机改造指南：闲置S905L3机顶盒，20分钟变身24小时在线的Armbian服务器

九联UNT402A刷机改造指南：闲置S905L3机顶盒，20分钟变身24小时在线的Armbian服务器【免费下载链接】amlogic-s9xxx-armbian Supports running Armbian on Amlogic, Allwinner, and Rockchip devices. Support a311d, s922x, s905x3, s905x2, s912, s905d… · 2026/11/2 15:03:31

支持手机端夸克不限速 - 免费永久解析直链~满速下载!!

今天教大家一招能解决夸克网盘限制的在线工具。这个工具也是完全免费使用的。下面让大家看看我用这个工具的下载速度咋样。地址获取：放在这里了，可以直接获取这个速度还是不错的把。对于平常不怎么下载的用户还是很友好的。下面开始今天的教学输入我给… · 2026/11/2 15:03:31

Dolphin-Mistral 24B威尼斯版：掌控你的无审查AI

Dolphin-Mistral 24B威尼斯版：掌控你的无审查AI 导语：Dolphin-Mistral 24B威尼斯版正式发布，这款由dphn.ai与Venice.ai联合打造的大语言模型以"无审查"和"用户控制权"为核心卖点，挑战现有AI服务模式&#xff… · 2026/11/2 15:03:31