秋招突击——算法打卡——5/24——无重复字符的最长字串

本文主要是介绍秋招突击——算法打卡——5/24——无重复字符的最长字串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

在这里插入图片描述

实现代码

// 无重复字符的最长子串
int lengthOfLongestSubstring(string s) {int l = 0,r = 0;int res = 0;unordered_map<char,int> temp;while(l < s.size()){temp[s.at(l)] = l;for (r = l + 1; r < s.size() ; r++) {if(temp.count(s.at(r))) break;else temp[s.at(r)] = r;}res = max(res,r - l);l ++;temp.clear();}return res;
}

这样做不就是暴力搜索吗，复杂度是n平方，有很多优化的地方
- 不满足条件的时候，并不一定需要重投开始遍历，至少你能确保你将要退出来的是有重复的，将要加进去的是没有重复的，这样就不是平方的运算复杂度，是n的复杂度。

更高效率的实现代码

在这里插入图片描述

双指针问题，通过单调性来优化，下面的代码写的真好看

int lengthOfLongestSubstring(string s) {unordered_map<char,int> heap;int res = 0;for (int i = 0 ,j = 0; i < s.size(); ++i) {heap[s[i]] ++;while(heap[s[i]] > 1)heap[s[j ++]] --;res = max(res,i - j + 1);}return res;
}