3. 无重复字符的最长子串
难度中等4774
给定一个字符串，请你找出其中不含有重复字符的 最长子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
示例 4:
输入: s = ""
输出: 0
提示：
0 <= s.length <= 5 * 10<sup>4</sup>-
s由英文字母、数字、符号和空格组成
My solution
import java.util.Arrays;
public class Solution {
public int lengthOfLargestSubstring(String s){
if(s.length()==0)
return 0;
int[] count=new int[s.length()];
String tmp = null;
for(int i=0;i<s.length();i++){
tmp="";
for(int j=i;j<s.length();j++){
if (tmp.contains(String.valueOf(s.charAt(j))))
break;
else
{
tmp+=s.charAt(j);
count[i]++;
}
}
}
Arrays.sort(count);
return count[s.length()-1];
}
}
执行用时：360 ms, 在所有 Java 提交中击败了5.20%的用户
内存消耗：39.3 MB, 在所有 Java 提交中击败了9.11%的用户
时间复杂度O(n^2)
空间复杂度O(n)
滑动窗口法
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> occ = new HashSet<Character>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
occ.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
}
i是窗口的左指针，rk是窗口的右指针，其中i是所指元素的序号，从0开始，而rk是所指元素序号-1.从-1开始；
刚开始i=0，不用从窗口去掉最左侧元素，而之后就需要移动左指针了；
当rk<s.length()-1并且哈希集合中不包含序号为rk+1的元素时，将这个元素添加进哈希集合，并且移动右指针；
在一次移动左指针的过程中，最后要给ans重新赋值，保证ans最后为滑动窗口的最大距离；
滑动窗口法的关键在于当第i个元素到第rk+1个元素，第rk+1的元素为最先出现的相同元素时，只需要将i向右移动一个位置，而不需要移动rk，因为此时i+1到rk之间肯定是没有重复字符的
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
