企业官网建设流程全解析

莱阳做网站,合肥seo招聘,南京移动网站设计,建筑信息平台查询简介 题目链接#xff1a;https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envTypeproblem-list-v2envId2cktkvj 解决方式#xff1a;滑动窗口#xff08;双指针 哈希#xff09; 这是作者学习众多大神的思路进行解题的…简介题目链接https://leetcode.cn/problems/longest-substring-without-repeating-characters/description/?envTypeproblem-list-v2envId2cktkvj解决方式滑动窗口双指针 哈希这是作者学习众多大神的思路进行解题的步骤很推荐大家解题的时候去看看题解里面大佬们的思路、想法推荐看powcai大佬的讲解其中包含了一系列问题如最小覆盖子串、无重复字符的最长子串、至多包含两个不同字符的最长子串等。滑动窗口classSolution{// 滑动窗口--双指针与哈希的结合// 双指针很难解决多个元素的一个状态或者差异// 此处对于无重复子串的判断涉及到多个位双指针无法或者很难办到// 这时候就可以借助哈希存储一定的规则信息来解决publicintlengthOfLongestSubstring(Strings){// 哈希存储迭代过程中的信息MapCharacter,IntegermapnewHashMap();// 特例if(snull||s.length()0)return0;intmax0;// 双指针intleft0;// 右指针同时遍历字符for(intright0;rights.length();right){if(map.containsKey(s.charAt(right))){// 如果当前迭代的元素处于滑动窗口中则将左指针跳到重复元素的右边即重复元素索引 1// 之所以可以这样是因为在没有重复元素之前迭代的过程已经把不重复的最大子串的长度记下了// 跳到滑动窗口中重复元素的右边开始新一轮的查找// 看看是否还有必之前的记录还大的不重复的子串leftMath.max(left,map.get(s.charAt(right))1);// 确保左指针不会回退即出现以前存在过的元素时左指针跳转回滑动窗口已经抛弃的部分}// 哈希存放字符以及对应的索引方便判断元素是否重复map.put(s.charAt(right),right);// 每次迭代都需存储当前无重复子串中较大的那个为了查到最大的那一位maxMath.max(max,(right-left)1);}returnmax;}}讲解// left Math.max(left, map.get(s.charAt(right)) 1);// 确保左指针不会回退即出现以前存在过的元素时左指针跳转回滑动窗口已经抛弃的部分leftmap.get(s.charAt(right))1;这个代码在处理abba这个测试用例时确实会输出3而正确答案应该是2最长无重复子串是 “ab” 或 “ba”。问题出在这一行这行代码的逻辑是当遇到重复字符时把左指针直接跳到「上一次出现该字符的位置」的下一位。这个逻辑在大多数情况下是对的但有一个致命缺陷它没有保证 left 只能向右移动而不会回退即在 right3 时执行leftmap.get(a)1;// map.get(a) 还是 0所以 left 1此时窗口变成 [1,3] → 对应子串是 “bba”长度 3然后计算maxMath.max(max,right-left1)Math.max(2,3-11)3所以最终返回了 3这就是 bug 所在。根本原因当遇到第二个 ‘a’ 时map 中存的还是第一次出现的 ‘a’ 的位置索引 0于是你把 left 跳到 1但实际上你当前的窗口左边界已经移动到 2 了你却把它拉回到了 1这就导致窗口错误地包含了跳转到之前已经“丢弃”的字符。正确做法left 不能回退标准写法是leftMath.max(left,map.get(s.charAt(right))1);这样就能保证 left 只向右移动不会倒退。总结出错的那一行是leftmap.get(s.charAt(right))1;// 错误可能导致 left 回退应该改成leftMath.max(left,map.get(s.charAt(right))1);// 正确这就是 LeetCode 3. 无重复字符的最长子串 经典滑动窗口的正确写法。记住滑动窗口的左指针永远只能右移不能左移。创作声明本文部分内容由AI辅助生成AIGC仅供参考