LeetCode 3：Longest Substring Without Repeating Charact
Given a string s, find the length of the longest substring without repeating characters.
说人话：
在一个字符串中寻找没有重复字母的最长子串。
举例1：
举例2：
举例3：
举例4：
[法1] 滑动窗口
思路
滑动窗口的思想是我们取 2 个索引 i 和 j ，这样就围成了一个窗口，窗口 s[i…j] 是没有重复字母的。
① 然后我们不断向右边扩展，直至字符串结束或者是遇到重复字符了。那么这个时候我们就暂时找到了一个符合条件的子串的，记下当前的子串长度。
② 然后我们从左边删除字符，直至字符串不包含即将从右边加入的字符的时候就停下。
这样我们就又可以执行 ① 来扩展子串了，这个循环 ① ② 直至结束。
算法
class Solution {
public int lengthOfLongestSubstring(String s) {
int result = 0;
//子串为 s[left...right]
int left = 0;
int right = -1;
while(left < s.length()){
//不断往后边加入满足条件的字符
while(right+1 < s.length() &&
!s.substring(left,right+1).contains(s.substring(right+1,right+2))){
right++;
}
//跳出循环，记录当前最长的子串长度
result = (result > (right-left+1))?result:(right-left+1);
//右边已经到底了，那就说明已经找到最长的了
if(right == s.length()-1){
break;
}
//不能往后边加的时候，从左边删，删到可以往后边加为止
while(left < s.length() &&
s.substring(left,right+1).contains(s.substring(right+1,right+2))){
left++;
}
}
return result;
}
}
提交结果
代码分析
- 时间复杂度：O(n)：实际上我们的 left 和 right 只是遍历了一遍字符串，所以时间复杂度只是 O(n)
- 空间复杂度：O(1)
改进思路
为什么 O(n) 的时间复杂度在 Leetcode 提交后执行用时这么久呢？其实是因为我们在判断字符串中是否存在某字符的时候用了 JDK 的 API：s.contains(substring)。这个 API 在判断的时候每次都会遍历我们整个字符串，这是比较耗时的，也是我们可以改进的地方。
[法2] 优化判断是否重复的逻辑
思路
ASCII 总共就 256 个，我们可以创建一个临时数组来记录字符串中的字符在 ASCII 中出现的频率，以此来判断是否存在重复字符。
代码
class Solution {
public int lengthOfLongestSubstring(String s) {
//记录字符出现频率
int[] freq = new int[256];
int result = 0;
//子串为 s[left...right]
int left = 0;
int right = -1;
while(left < s.length()){
//不断往后边加入满足条件的字符
while(right+1 < s.length() && freq[s.charAt(right+1)] == 0){
right++;
freq[s.charAt(right)] ++;
}
//跳出循环，记录当前最长的子串长度
result = (result > (right-left+1))?result:(right-left+1);
//右边已经到底了，那就说明已经找到最长的了
if(right == s.length()-1){
break;
}
//不能往后边加的时候，从左边删，删到可以往后边加为止
while(left < s.length() && freq[s.charAt(right+1)] > 0){
freq[s.charAt(left)] --;
left++;
}
}
return result;
}
}
提交结果
代码分析
- 时间复杂度：O(n)，优化后我们的时间复杂度还是一样的，但是省去了底层遍历字符串，大大减少了执行同时。
- 空间复杂度：用了存储字符使用频率的临时数组，O(256) = O(1)