力扣3 ：无重复最长子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/submissions/

1.暴力法

直接使用两层循环，第一层 i 用来遍历整个字符串，第二层 j 用来向后移动，寻找最长不重复子串。j 每向后移动一个都和前面每个字符做一次比较看是否重复。
代码

#include <iostream>

using namespace std;

 int lengthOfLongestSubstring(string s) {
    int length = 1; // 记录当前无重复子串的长度
    int _max = 1;   // 记录最大无重复子串的长度
    bool flag = true;  //用来结束两层循环
    if(s.empty()){
		return 0;
    }

    for(int i = 0;i < s.size();i++){
		length = 1;
		flag = true;
		// 第二层循环 j指针向后移 并不断比较和前面是否重复
		for(int j = i + 1;j < s.size() && flag;j++){
			for(int k = i;k < j;k++){
				// 如果和前面重复 记录长度 不再继续比较
				if(s[j] == s[k]){
					length = j - i;
					if(_max < length){
						_max = length;
					}
					flag = false; // 结束j的循环
					i = k ;   // i 从重复的字符开始比较
					break;
				}else if(k == j-1){  // 比较到最后仍不重复
					length = j - i + 1; // 记录长度
					if(_max < length){
						_max = length;
					}
				}
			}
		}
    }
    return _max;
}


int main()
{
	string str = "";
	cin >> str;
    cout<<lengthOfLongestSubstring(str);
    return 0;
}

2.使用vector

借鉴了另一个博主的思路，链接
1 遍历字符串中的每个字符，创建一个vector容器，如果容器中没有当前字符则将其加入vector
2.如果容器中有当前字符则先记录当前不重复子串长度，然后擦去重复字符之前的字符。
3.重复上述步骤，直到遍历完整个字符串。

#include <iostream>
#include <vector>
using namespace std;

 int lengthOfLongestSubstring(string s) {
	int n = s.length();
	vector<char>vec;
	char c = 0;
	int mlen = 0;

	for(int i = 0;i < n;i++){
		c = s[i];
		for(int j = vec.size() - 1;j >= 0;j--){
			if(c == vec[j]){
				if(vec.size() > mlen){
					mlen = vec.size();
				}
				vec.erase(vec.begin(),vec.begin()+j+1);
				break;
			}
		}

		vec.push_back(c);
	}
	if(vec.size() > mlen){
		mlen = vec.size();
	}

	return mlen;

}


int main()
{
	string str = "";
	cin >> str;
    cout<<lengthOfLongestSubstring(str);
    return 0;
}

3.暴力法优化

#include <iostream>

using namespace std;

 int lengthOfLongestSubstring(string s) {
    int length = 1; // 记录当前无重复子串的长度
    int _max = 1;   // 记录最大无重复子串的长度

    if(s.empty()){
		return 0;
    }
    if(s.length() == 1){
		return 1;
    }

    int _begin = 0;
    for(int _end = 1;_end < s.size();_end++){
		for(int index = _end - 1;index >= _begin;index--){
			if(s[index] == s[_end]){
				length = _end - _begin;
				_begin = index + 1;
				if(length > _max){
					_max = length;
				}
				break;
			}
			else if(index == _begin){
				length = _end - _begin + 1;
				if(length > _max){
					_max = length;
				}
			}
		}
    }
    return _max;
}


int main()
{
	string str = "";
	cin >> str;
    cout<<lengthOfLongestSubstring(str);
    return 0;
}