class Solution { public: int lengthOfLongestSubstring(string s) { map<char,int> hash; int ans = 0; int n= s.size(); for(int i= 0, j=0;j<n;j++){ if(hash.find(s[j])!=hash.end()) i=max(hash.find(s[j])->second+1,i); //当发现重复字符时,i直接跳到重复字符的下一位,改进了方法2中一个字符一个字符滑动窗口的方法 ans=max(ans,j-i+1); hash[s[j]]=j; } return ans; } };
时间: 2024-04-05 17:35:22 浏览: 7
这是一个使用滑动窗口算法解决无重复字符的最长子串问题的C++代码,使用了哈希表存储字符出现的位置。算法的时间复杂度为O(n),其中n为字符串的长度。代码中的map容器是C++ STL中的关联容器,用于存储键值对,本代码中用来存储字符出现的位置。在遍历字符串时,维护两个指针i和j,分别表示子串的起始和结束位置,同时使用哈希表判断字符是否重复出现。当发现重复字符时,i直接跳到重复字符的下一位,避免了一个字符一个字符滑动窗口的方法,提高了算法的效率。最后返回最长子串的长度。
相关问题
class Solution {public: int lengthOfLongestSubstring(string s) { if(s.size() == 0) return 0; 讲解该代码
这是一段求解最长无重复子串长度的代码,下面对其进行讲解:
```
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.size() == 0) return 0; // 如果字符串为空,返回0
```
首先判断给定的字符串s是否为空,如果为空,那么最长无重复子串的长度为0。
```
int maxLen = 1; // 最长无重复子串的长度最小为1
int start = 0; // 子串的起始位置
int end = 0; // 子串的结束位置
int n = s.size(); // 字符串s的长度
unordered_set<char> hash; // 用一个哈希表记录出现过的字符
while(end < n){
if(hash.find(s[end]) == hash.end()){ // 如果当前字符不在哈希表中,将其加入哈希表
hash.insert(s[end]);
end++; // 将子串的结束位置向右移动
maxLen = max(maxLen, end - start); // 更新最长无重复子串的长度
}else{ // 如果当前字符在哈希表中,就将子串的起始位置向右移动,直到子串中不包含当前字符为止
hash.erase(s[start]);
start++;
}
}
return maxLen; // 返回最长无重复子串的长度
}
};
```
接下来,定义三个变量maxLen、start和end,分别表示当前最长无重复子串的长度、子串的起始位置和子串的结束位置。同时,定义一个哈希表hash,用于记录已经出现过的字符。
接着,用while循环遍历整个字符串s,如果当前字符不在哈希表中,就将其加入哈希表,并将子串的结束位置向右移动。如果当前字符在哈希表中,就将子串的起始位置向右移动,直到子串中不包含当前字符为止。在子串的每一个位置,都要更新一下最长无重复子串的长度maxLen。
最后,返回最长无重复子串的长度maxLen。
Java语言中下面哪个是编译正确的()A.List<String>list=new ArrayList<Integer>(); B.Map<String.Object>map=newHash<String.String>();
在Java语言中,下面的选项是编译正确的:
A. List<String> list = new ArrayList<Integer>();
这是因为Java中的泛型是类型安全的,编译器会在编译时进行类型检查。在这个选项中,虽然ArrayList的类型参数是Integer,但是它可以被赋值给List<String>,因为Integer是String的子类。编译器会自动进行类型转换,将Integer转换为String。
另一方面,选项B是错误的:
B. Map<String, Object> map = new Hash<String, String>();
这是因为在创建HashMap对象时,类型参数必须与Map接口的类型参数一致。在这个选项中,Hash<String, String>的类型参数与Map<String, Object>不匹配,因此会导致编译错误。