如何用公司名称搜到公司网站,上海网安备案网站,通信工程企业网站建设,忘记了wordpress登录密码怎么办文章目录题目描述思路 代码1. 之前的版本更新 2.0题目描述
子串#xff1a;各字符间必须要相邻#xff0c;而非子序列使用滑动窗口来做就行
思路 代码
1. 之前的版本
思路#xff1a;维护一个滑动窗口#xff0c;滑动窗口中容纳一个无重复字符的…
文章目录题目描述思路 代码1. 之前的版本更新 2.0题目描述
子串各字符间必须要相邻而非子序列使用滑动窗口来做就行
思路 代码
1. 之前的版本
思路维护一个滑动窗口滑动窗口中容纳一个无重复字符的子串。滑动窗口左边界移动的情况 【abc】 a a【bca】【abcd】 c abc【dc】 其实以上两种情况殊途同归都是把左边界换成当前判断字符在HashMap中对应的下标的位置的后一个。 然后把前面的字符全都丢弃即可在HashMap中remove()。左边界移动的情况需要进行长度的判断当前滑动窗口长度可能会改变如果比当前存储的最大长度要大那么就需要更新。为什么可以这样子特别记录一下这道题其实老早就通过了。。但是之后考虑情况多了出现了觉得自己写的代码其实考虑不周但是就是过了的情况 。 主要是有这个注意点在上面的左边界移动情况2考虑到abc都被丢弃但是有没有可能a、b实际上可能可以创造最长子串呢 答案是没有因为实际上最多的长度【abcd】已经被记录下来了b最多就是【bcd】c的情况a也同理因此已经可以直接丢弃掉了。
class Solution {public int lengthOfLongestSubstring(String s) {int len0, lenNow0;HashMapCharacter,Integer hashMap new HashMap();for(int i0;is.length();i){if(hashMap.containsKey(s.charAt(i))){// 和left.char相同的情况下可以继续// 这个if是个优化但是其实删掉也可以之后的代码对于这种情况达到一样的效果if(hashMap.get(s.charAt(i))i-lenNow){hashMap.put(s.charAt(i),i);continue;}// 否则需要把前面的全删了len Math.max(len,lenNow);// 获取当前重复值的下标。int temp hashMap.get(s.charAt(i));// 维护哈希表把不需要的映射remove掉。for(int j i-lenNow;jtemp;j){hashMap.remove(s.charAt(j),j);}// 更新当前滑动窗口的长度lenNow i - temp;hashMap.put(s.charAt(i),i);}else{hashMap.put(s.charAt(i),i);lenNow;}}// 一直数到字符串结束的情况补一个补充return Math.max(len,lenNow);}
}时间复杂度O(N)实际上整个流程本质上就是对字符串的每一个元素都必然访问一次可能删除一次。空间复杂度O(字符集的大小)因为我们需要简历哈希表而表最大的情况下会容纳整个字符集及对应下标。
更新 2.0
比较精简的代码
class Solution {public int lengthOfLongestSubstring(String s) {// initint len s.length();int max 0;char[] arr s.toCharArray();// 字符字符出现下标MapCharacter, Integer hashmap new HashMap();int windowLeft 0;for(int i 0; i len; i) {// Case 1 重复if(hashmap.containsKey(arr[i])) {int index hashmap.get(arr[i]);for(int j windowLeft; j index; j) {hashmap.remove(arr[j]);}windowLeft index 1;hashmap.put(arr[i], i);}// Case 2 没重复else {hashmap.put(arr[i], i);max Math.max(max, hashmap.size());}}return max;}
}
