制作手机网站工具,软件项目交易平台,国家和城乡建设部网站首页,网页版微信仅传输文件1. 题目
给定一个字符串#xff0c;请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc#xff0c;所以其长度为 3。
示例 2:输入: bbbbb
输出: 1
解释: 因为无重复…1. 题目
给定一个字符串请你找出其中不含有重复字符的 最长子串 的长度。示例 1:输入: abcabcbb
输出: 3
解释: 因为无重复字符的最长子串是 abc所以其长度为 3。
示例 2:输入: bbbbb
输出: 1
解释: 因为无重复字符的最长子串是 b所以其长度为 1。
示例 3:输入: pwwkew
输出: 3
解释: 因为无重复字符的最长子串是 wke所以其长度为 3。请注意你的答案必须是 子串 的长度pwke 是一个子序列不是子串。2. 代码
1. 滑动模块法
核心思想
i表示的是不重复子串的起始位置一般i是不会变化的 当检查不出来i~j之间有相同的元素的时候i一直等于0 如abcabd 起始 i 0 j 0 k i j处于一直增加的状态 k就从不变的i和j之间一直检测其实一般有重复就会是第一个 所以直接break
class Solution {
public:int lengthOfLongestSubstring(string s) {int size, i0, j, k, max0; size s.size(); // 让i一直代表着最长不重复字符串的头k用来检验从i到j中是不是有重复的字符。若有则ik1i直接定位到重复k的后一个for(j 0; jsize; j){ for(k i; kj; k) if(s[k] s[j]){i k 1;break;}if(j-i1 max) //如果没有重复则j表示的是尾巴i表示的是头j-i1即可max j - i 1;}return max;}
};
2. 暴力法
find函数会返回字符在s中的位置
核心思想 两个for循环表示取所有的子串 新建立的函数表示的是检测子串是不是有重复的值新建立的函数参数是原s和子串的起始位置
class Solution {
public:int lengthOfLongestSubstring(string s) {int n s.length();int ans 0;int m;for(int i 0; in; i) { for(int j i 1; j n; j) { if(allUnique(s, i, j)) {ans max(ans, j - i);int m j-i;}}}return m;}public: bool allUnique(string s, int start, int end) {string str ;for(int i start; i end; i) {char c s[i];if(str.find(c) 0) {return false;}str[i] c;}return true;}
};