给定一个字符串，找出最长的不具有重复字符的子串的长度。例如，“abcabcbb”不具有重复字符的最长子串是“abc”，长度为3。对于“bbbbb”，最长的不具有重复字符的子串是“b”，长度为1。
[编程题]找出最长不重复字符的子串
private int max_len = 0;
public int lengthOfLongestSubstring (String s){
for(int i = 0; i < s.length(); i++){
int len = 1;
String str = "" + s.charAt(i);
for(int j = i+1; j < s.length(); j++){
String ch = "" + s.charAt(j);
if(str.contains(ch)){
break;
}else{
str = str.concat(ch);
len++;
}
}
if(max_len < len){
max_len = len;
}
}
if(s.length() == 0){
return 0;
}else{
return max_len;
public int lengthOfLongestSubstring (String s){
for(int i = 0; i < s.length(); i++){
int len = 1;
String str = "" + s.charAt(i);
for(int j = i+1; j < s.length(); j++){
String ch = "" + s.charAt(j);
if(str.contains(ch)){
break;
}else{
str = str.concat(ch);
len++;
}
}
if(max_len < len){
max_len = len;
}
}
if(s.length() == 0){
return 0;
}else{
return max_len;
}
}
发表于 2020-06-30 15:26:13
回复(0)
public int lengthOfLongestSubstring (String s) {
if(null == s|| s.length() ==0)return 0;
if(s.length() == 1) return 1;
int result =0;
HashSet<Character> existSet = new HashSet<>();
int len = s.length();
int left = 0;
int right= 0;
while(right<len){
if(existSet.contains(s.charAt(right))){
result = Math.max(result,right-left);
left++;
right = left;
existSet.clear();
}else{
existSet.add(s.charAt(right));
right++;
}
}
return result;
}
发表于 2020-06-19 21:04:08
回复(0)
public class Solution {
public int lengthOfLongestSubstring (String s) {
// write code here
int[] user = new int[128];
int left = 0;
int right = 0;
int result = 0;
int res = 0;
for(int i=0;i<s.length();i++){
char temp = s.charAt(i);
if(user[temp] == 0){
user[temp] = 1;
result = result + 1;
res = res>result?res:result;
}else{
for(int j=left;j<s.length();j++){
if(temp == s.charAt(j)){
left = j+1;
break;
}else{
result = result - 1;
user[s.charAt(j)] = 0;
}
}
}
}
return res;
}
} 两个滑动指针，
编辑于 2020-06-06 17:22:19
回复(0)
public class Solution {
public int lengthOfLongestSubstring(String s) {
return longestSubstring(s,s.length());
}
public int longestSubstring(String A, int n) {
if(A == null || n < 2){
return n;
}
char[] chas = A.toCharArray();
int[] map = new int[256];
for (int i = 0; i < 256; i++) {
map[i] = -1;
}
int len = 0;
int pre = -1;
int cur = 0;
for (int i = 0; i < n; i++) {
pre = Math.max(pre, map[chas[i]]);
cur = i - pre;
len = Math.max(len, cur);
map[chas[i]] = i;
}
return len;
}
}
发表于 2019-11-17 21:22:33
回复(0)
import java.util.HashSet;
public class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int i = 0;
int j = 0;
int maxLen = 0;
HashSet<Character> set = new HashSet<>();
while (i <= j && j < s.length()) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j));
j++;
maxLen = Math.max(maxLen, j - i);
} else {
set.remove(s.charAt(i));
i++;
}
}
return maxLen;
}
}
发表于 2019-11-04 19:20:14
回复(3)
/*滑动窗口设计思想：
创建一个ArrayList类型的list，遍历字符串，一个个将字符加入进来，遇到重复的字符，则执行回退操作，然后清空list
进入下一个循环，继续将不重复的字符加入进去。
每次需要记下list的大小，比较得到最长的longest subString的长度
比如字符串“wlrbbmqcmdghy”
窗口变化情况为：“wlrb” -> “bmqc” ->"qcmdghy"
（1）list窗口包含字符串“wlrb”，继续遍历发现重复的字符b，则索引i退回到第一个字符b的位置，即3，清空list
（2）i++，当前索引位置前进一位变为4，即遍历到第二个b字符，从第二个b字符开始遍历，加入不重复的字符
（3）list窗口包含字符串“bmqc”,继续遍历发现重复的字符m,则索引i退回到第一个字符m的索引位置，即5，情况list
（4）i++，索引前进一位，遍历到第字符q字符，从字符q开始遍历，加入不重复的字符
*/
import java.util.ArrayList;
public class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0)
return 0;
int len = s.length();
int longest_len = 0;
ArrayList<Character> list = new ArrayList<>();
for(int i = 0; i < len; i++){
if(!list.contains(s.charAt(i))){
list.add(s.charAt(i));
//每次比较得到最大长度
if(list.size() > longest_len){
longest_len = list.size();
}
}
//回退到重复的字符位置，并清空list
else{
int inner_index = list.indexOf(s.charAt(i));
i = i - (list.size() - inner_index);
list.clear();
}
}
return longest_len;
}
}
编辑于 2019-07-19 18:17:53
回复(0)
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> map = new HashMap<>();
int start = 0, max = 0;
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
//如果当前元素与滑动窗口中的元素重复：
if(map.containsKey(c) && map.get(c) >= start) {
max = Math.max(max, i - start);
start = map.get(c) + 1;
//如果当前元素与滑动窗口中的元素不重复，但已经遍历到了最后一个字符：
}else if(i == s.length() - 1) max = Math.max(max, i - start + 1);
map.put(c, i);
}
return max;
}
HashMap包含所有已遍历的元素，但只有索引（hashmap中entry的value）大于滑动窗口左边界（start)的元素才是滑动窗口中的元素
发表于 2019-05-19 18:34:58
回复(0)
滑动窗口保存每次滑动的字符及最大子串长度，通过HashMap实现。
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s==null || s.length()==0)
return 0;
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
int leftBound = 0;
int maxLen = 0;
for(int i=0;i<s.length();i++){
char c = s.charAt(i);
leftBound = Math.max(leftBound,(map.containsKey(c))?map.get(c)+1:0);
maxLen = Math.max(maxLen,i-leftBound+1);
map.put(c,i);
}
return maxLen;
}
}
发表于 2019-01-02 09:52:43
回复(0)
import java.util.*;
public class Solution {
public int lengthOfLongestSubstring(String s) {
ArrayList<Character> list = new ArrayList<Character>();
int n= s.length();
int max=0;
for(int i=0;i<n;i++){
if(!list.contains(s.charAt(i))){
list.add(s.charAt(i));
max= Math.max(max,list.size());
}
else{
list.remove(0);
i--;
}
}
return max;
}
}
public class Solution {
public int lengthOfLongestSubstring(String s) {
ArrayList<Character> list = new ArrayList<Character>();
int n= s.length();
int max=0;
for(int i=0;i<n;i++){
if(!list.contains(s.charAt(i))){
list.add(s.charAt(i));
max= Math.max(max,list.size());
}
else{
list.remove(0);
i--;
}
}
return max;
}
}
发表于 2018-07-12 16:05:48
回复(0)
这题用暴力时间会超，用这种O(N)时间复杂度，两个指针i,j，i 负责遍历从前往后遍历所有的字符，j 负责滑动到与第i个不重复的位置，这种方式称为“Sliding Window”。import java.util.*;public class Solution {public int lengthOfLongestSubstring(String s) {if(s == null || s.isEmpty()){return 0;}int len = s.length();int i = 0,j = 0,ans = 0;HashSet<Character> set = new HashSet<Character>();while(i < len && j < len){if(!set.contains(s.charAt(j))){set.add(s.charAt(j++));ans = Math.max(ans,j-i);}else{set.remove(s.charAt(i++));}}return ans;}}
发表于 2017-08-11 09:49:24
回复(2)
import java.util.Hashtable;
public class Solution {
public int lengthOfLongestSubstring(String s) {
int start=0;
Hashtable<Character,Integer> ht=new Hashtable<Character,Integer>();
int maxl=0;
for(int i=0;i<s.length();i++){
if(ht.containsKey(s.charAt(i))){
int end=ht.get(s.charAt(i));
for(int j=start;j<=end;j++){
ht.remove(s.charAt(j));
}
start=end+1;
ht.put(s.charAt(i),i);
}
else{
ht.put(s.charAt(i),i);
maxl=Math.max(i-start+1,maxl);
}
}
return maxl;
}
}
发表于 2017-05-25 19:40:20
回复(0)
the basic idea is, keep a hashmap which stores the characters in string as keys and their positions as values, and keep two pointers which define the max substring. move the right pointer to scan through the string , and meanwhile update the hashmap. If the character is already in the hashmap, then move the left pointer to the right of the same character last found. Note that the two pointers can only move forward.
public int lengthOfLongestSubstring(String s) { if (s.length()==0) return 0; HashMap<Character, Integer> map = new HashMap<Character, Integer>(); int max=0; for (int i=0, j=0; i<s.length(); ++i){ if (map.containsKey(s.charAt(i))){ j = Math.max(j,map.get(s.charAt(i))+1); } map.put(s.charAt(i),i); max = Math.max(max,i-j+1); } return max; }
发表于 2017-03-13 00:36:39
回复(0)
问题信息
难度：
14条回答
121收藏
26285浏览
通过挑战的用户
查看代码-
2023-03-07 21:35:22
-
2023-02-24 21:59:21
-
2023-02-10 16:36:38 -
2022-11-07 12:49:41
-
2022-11-05 19:43:27
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
