【LeetCode】3. 无重复字符的最长子串

时间:2022-01-18 15:58:07

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
  请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

思路分析:

(1)首先要理解一个思路,如果[i,j]是不重复的,那么要判断[i,j+1]是否重复,就只要判断[j+1]在[i,j]是否存在,越界检查。

这里的计算就是:

设'abcabcbb',len=8,

从(0,1)(含左不含右)开始,不等于len,进入else条件,'a'不包括下一个字符'b',依次循环,

到了(0,3)的时候,str="abc",包含下一个字符'c',result="abc",跳出循环,

进入(1,2),str="b",一直到(1,4),包含下一个字符'b',result长度等于str长度,所以result不变。跳出循环,

进入(2,3),str="c",依次循环,最后一直到最后str的长度也没有超过result。最终得出result为abc,所以长度为3。

时间复杂度:O(n^2)

空间复杂度:O(n^2)

代码:

class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
String result = ""; //最长的不重复子串
String str = ""; //子串
for(int i=;i<len;i++){
for(int j=i+;j<=len;j++){
str = s.substring(i,j); //嵌套循环截取子串
if(j==len){ //截取带最后进行对比
result = result.length()<str.length()?str:result;
break;
}else{ //如果没有到最后就判断下一位是否在子串中
if(str.indexOf(s.substring(j,j+))>-){
result = result.length()<str.length()?str:result;
break;
}
}
}
}
return result.length();
}
}

(2)利用HashMap解题思路:

举个例子:s="abcbadca"; i= 0;j=0

依次把{a:1,b:2,c:3}存入map,此时ans = 3,i=0,j=3;

下一次进入的时候,因为‘b'已存在map中,所以i会被设为2,即字符数组中第一个b的后一个位置。同时map里面的b对应的值会被更新为4,然后判断ans的值,同时map里面的b对应的值会被更新为4。

依次计算,就可以把最长不重复子串的长度得出。这里只有一个循环,map的查找时间复杂度为O(1),比之前的两种方法都快。

时间复杂度:O(n);

空间复杂度:O(1)       //因为字符的总个数是固定的,所以map的长度也是固定的常数;

代码:

public class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = ;
Map<Character, Integer> map = new HashMap<>(); //存放字符数组和索引,key:char,value:index
for (int j = , i = ; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i); //包含下一个字符就把i移到相同字符的后一个位置
}
ans = Math.max(ans, j - i + ); //判断长度是否要改变
map.put(s.charAt(j), j + ); //把字符和索引放进map,重复的会进行覆盖
}
return ans;
}
}