LC第41题(好像不是41题qwq)：最长无重复子数组
解题思路
使用哈希表来记录不重复的数字，并开始用快指针遍历数组。如果快指针遍历到了滑动窗口内已经出现过的元素，就把慢指针指向的坐标值+1. 不要忘了更新hash[arr[i]] = i 哦！最后返回值为max(ans, i - left + 1)。
代码如下：
int maxLength(vector<int>& arr) {
// write code here
int ans = 0;
int left = 0;
unordered_map <int, int> hash;
if(arr.size() < 2) return arr.size();
for(int i = 0; i < arr.size(); i++)
{
if(hash.find(arr[i]) != hash.end() && hash[arr[i]] >= left)
{
left = hash[arr[i]] + 1;
}
ans = max(ans, i - left + 1);
a[arr[i]] = i;
}
return ans;
}
LC第3题：最长无重复子串
题目详情
给定一个字符串 s ，找出不含有重复字符的最小字串长度。
解题思路
-
遇到这种题要首先厘清“子数组”和“子串”和“子序列”的区别——子数组和子串是连续的，而子序列只需要是顺序的就可以，并不要求一定是连续的。
-
其次还是滑动窗口的概念——什么是滑动窗口？
滑动窗口其实就是一个队列。比如 s = “abcabcbb” ，进入这个队列为 abc 满足题目要求，当再进入 a ，队列就变为abca，就不满足要求了。所以我们需要移动队列。 如何移动呢？ 如果队列右边新进的元素已经出现在队列中了，那么就把队列最左侧元素移除，之后继续执行本判断，直到满足要求为止。 遍历到最后，然后求所有队列长度的最大值即可。
代码如下：
int lengthOfLongestSubstring(string s)
{
if(s.size() == 0) return 0;
unordered_set<char> res;
int maxStr = 0;
int left = 0;
for(int i = 0; i < s.size(); i++)
{
while(res.find(s[i]) != res.end())
{
res.erase(s[left]);
left++;
}
maxStr = max(maxStr, i - left + 1);
res.insert(s[i]);
}
retun maxStr;
}
void main() {
string s = "abcchubwab";
lengthOfLongestSubstring(s);
cout << s << endl;
//return 0;
}
