本文主要是介绍leetcode notes：longest substring without repeating charactors，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.
Example 2:
Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.
Example 3:
Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.
本来对题目也没有什么思路，因此看了一下官方题解，由于官方题解中均为java语言描述，根据解释转换为C++语言描述，如下：
方法一：暴力法
两个函数，一个函数用来求解子串并找出最长无重复字符子串，一个函数用来判断是否是无重复字符的子串。
假设我们有一个函数 bool allUnique(String substring) ，如果子字符串中的字符都是唯一的，它会返回true，否则会返回false。 我们可以遍历给定字符串 s 的所有可能的子字符串并调用函数 allUnique。 如果事实证明返回值为true，那么我们将会更新无重复字符子串的最大长度的答案。
1、为了枚举给定字符串的所有子字符串，我们需要枚举它们开始和结束的索引。
设开始和结束的索引分别为 i和 j。那么我们有 0≤i<j≤n 。因此，使用 i 从 0 到 n-1 以及 j 从 i ( 不从i+1开始，是为了适应字符串是重复一个字符的情况 )到 n 这两个嵌套的循环，我们可以枚举出 s 的所有子字符串。
2、要检查一个字符串是否有重复字符，我们可以使用集合。
我们遍历字符串中的所有字符，并将它们逐个放入 set 中。在放置一个字符之前，我们检查该集合是否已经包含它。如果包含，我们会返回 false。循环结束后，我们返回 true。
分析下面的程序可以发现，使用集合set是一个很巧妙的方法。因为常规上，我肯定是将复制一个string s，双层循环检查重复字符。而使用vector集合，可以减少不必要的空间，检查重复字符并不需要将字符串全部复制！在检查重复字符上，两种方法时间复杂度相同，空间复杂度不同。显然，使用集合set的空间复杂度更小。
程序分别为：
bool allUnique(string s, int start, int end)
{vector<int> set;set.push_back(s[start]);for (int i = 1; i < end-start+1; ++i){for (int j = 0; j < set.size(); ++j){if (set[j] == s[start+i]){return false;}}set.push_back(s[start+i]); }return true;
}
int Solution::lengthOfLongestSubstring(string s)
{int len = s.length();/*if (len == 1) //空字符串" "或单个字符的情况【其实这段语句是根据测试数据加的】{return 1;}(如果下面那段双循环中是i < len-1，这段话就不能被注释！其实就是自己的逻辑错了)*/int ans = 0;for (int i = 0; i < len; ++i){for (int j = i; j < len; ++j){if (allUnique(s, i, j)){ans = max(j-i+1, ans);}}}return ans;
}
复杂度分析：
方法二：滑动窗口
这篇关于leetcode notes：longest substring without repeating charactors的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
