秋招突击——算法打卡——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;
}

• 这个和我的差不多，都使用了双指针的，按时我没有优化，应该记录一下，他这里写的很简洁，很棒，最后一直将j移动到i重复出现的位置，但是也是一次一次迭代过去的，不够快。

分析总结

• 这次写的还行，但是逻辑没有理清楚，导致出现了很多问题，调整就调了大半天。

这篇关于秋招突击——算法打卡——5/24——无重复字符的最长字串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---