给定一个字符串，找出最长的不具有重复字符的子串的长度。例如，“abcabcbb”不具有重复字符的最长子串是“abc”，长度为3。对于“bbbbb”，最长的不具有重复字符的子串是“b”，长度为1。
[编程题]找出最长不重复字符的子串
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int len = s.length();
if(len==0) return 0;
int maxLen = 0,left = 0;
unordered_map<char,int> charMap;
for(int i=0;i<len;i++)
{
if(charMap.find(s[i]) != charMap.end())
left = max(left,charMap[s[i]]+1);
maxLen = max(maxLen,i-left+1);
charMap[s[i]] = i;
}
return maxLen;
}
};
发表于 2017-07-12 21:11:58
回复(0)
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
const int ASCII=26;
int last[ASCII];
int start=0;
fill(last,last+ASCII,-1);
int max_len=0;
for(int i=0;i<s.size();++i)
{
if(last[s[i]-'a']>=start)
{
max_len=max(i-start,max_len);
start=last[s[i]-'a']+1;
}
last[s[i]-'a']=i;
}
return max((int)s.size()-start,max_len);
}
};
发表于 2017-11-23 16:23:43
回复(0)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
map<char , int> strMap;
int num = 0;//最大substring的size，初始化为0
int start = -1;//起始点坐标
for(int i = 0;i<s.size();i++)
{
if(strMap.count(s[i]) != 0)
{
start = max(start,strMap[s[i]]);//删除左边界的无用点
}
strMap[s[i]] = i;
num = max(num,i-start);//计算size
}
return num;
}
};
发表于 2017-03-02 20:13:32
回复(0)
public class Solution {
/**
* @param s: a string
* @return: an integer
*/
public int lengthOfLongestSubstring(String s) {
// write your code here
int[] cnt = new int[256];
char[] sc = s.toCharArray();
int ans = 0;
for(int l = 0, r = 0; r < sc.length; r++){
cnt[sc[r]]++;
// 找到第一个重复的字符
while(cnt[sc[r]] > 1){
cnt[sc[l]]--; //将前面的字符重置
l++;
}
ans = Math.max(ans, r - l + 1);
}
return ans;
}
}
发表于 2018-09-09 15:17:38
回复(2)
简单 易理解的写法 滑动窗口
class Solution {
public int lengthOfLongestSubstring(String s) {
//滑动窗口 思路 维护1个HashSet(window) window装当前窗口的字符统计
if(s.length() == 0){
return 0;
}
if(s.length() == 1){
return 1;
}
int res = 0;
HashSet<Character> window = new HashSet<>();
int l=0;
int r=0;
while(r<s.length()){
char ch = s.charAt(r);
//如果新元素窗口内存在 就需要不断地缩小窗口，直到这个元素不存在
while(l<r && window.contains(ch)){
window.remove(s.charAt(l));
l++;
}
//添加完元素后，就开始统计最大长度
window.add(ch);
res = Math.max(res,r-l+1);
r++;
}
return res;
}
}
发表于 2022-07-21 20:41:04
回复(0)
//可以考虑一下暴力求解
class Solution {
public:
/**
*
* @param s string字符串
* @return int整型
*/
int lengthOfLongestSubstring(string s) {
// write code here
if(s.empty()||s.size()==0)
return 0;
int len = s.length();
int start = -1;
int end = -2;
//遍历所有的可能子串
for(int i = 0;i<len;i++)
{
for(int j = i+1;j<=len;j++)
{
int flag = 1;
//注意substring(i,j)是[i,j),左闭右开
string str = s.substr(i,j-i);
//判断是否存在重复的字符
for(int k = 0; k < str.length();k++)
for(int l = k+1;l<str.length();l++)
{
if(str[l]==str[k])
flag = 0;
}
//当不存在重复的字符
if(flag==1)
{
//判断是不是比当前的串长
if((j-i)>=(end-start))
{
start = i;
end = j;
}
}
}
}
return end-start;
}
};
发表于 2020-07-28 17:20:23
回复(0)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
// write code here
map<char, int> gone;
int start = 0, maxl = 0, ans = 0;
for(int i=0; i<s.size(); ++i){
auto it = gone.find(s[i]);
if(it == gone.end() || it->second < start)
gone[s[i]] = i, ++maxl;
else{
ans = max(maxl, ans);
maxl -= it->second - start;
start = it->second+1;
it->second = i;
}
}
return max(maxl, ans);
}
};
发表于 2020-07-10 20:55:12
回复(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) {
int count[] = new int[128];
int maxlength = 0;
int start = 0;
for(int i=0; i<s.length(); i++){
char ch = s.charAt(i);
count[(int)ch]++;
if(count[ch]>1){
maxlength = Math.max(maxlength, i - start);
while(s.charAt(start) != ch){
count[s.charAt(start)] --;
start++;
}
count[ch]--;
start++;
}
}
maxlength = Math.max(maxlength, s.length() - start);
return maxlength;
}
发表于 2018-08-03 22:19:53
回复(0)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int freq[256] = { 0 };//记录是否出现
int l = 0, r = -1;
int res = 0;
while (r+1<s.size())
{
if (freq[s[r + 1]] == 0)//没出现过 标记为出现 后移r
{
freq[s[r + 1]] = 1;
r++;
}
else //出现过 清除l所在位置字符 后移l
{
freq[s[l]] = 0;
l++;
}
res = max(res, r - l + 1);
}
return res;
}
};
编辑于 2018-05-29 20:53:59
回复(0)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int len = s.length();
int freq[256] = {0};
int i = 0;
int j = -1;
int max_len = 0;
while(i < len){
if(j+1 < len && freq[s[j+1]] == 0){
++freq[s[++j]];
}else{
max_len = max(max_len, j-i+1);
--freq[s[i++]];
}
}
return max_len;
}
};
发表于 2018-04-02 21:48:58
回复(0)
/*public int lengthOfLongestSubstring(String s) {
if(s==null||s.length()==0) return s.length();
int max=0;
HashMap<Character, Boolean> map =new HashMap<Character,Boolean>();
Queue<Character> queue =new LinkedList<Character>();
for(int i=0;i<s.length();i++){
char ch =s.charAt(i);
if(map.containsKey(ch)){
if(map.get(ch)==true) {//有重复的值
if (queue.peek() ==ch){//第一个重复
queue.poll();
queue.add(ch);
}
else{//除了第一个重复
while(!queue.isEmpty()&&queue.peek()!=ch){//除了那个重复的值
char c= queue.poll();
map.put(c,false);
}
}
}
else{
queue.add(ch);
map.put(ch,true);
max=max<queue.size()?queue.size():max;
}
}
else{
map.put(ch,true);
queue.add(ch);
max=max<queue.size()?queue.size():max;
}
}
return max;
}*/
//参考大牛解法
public int lengthOfLongestSubstring(String s) {
if(s==null||s.length()==0) return s.length();
int left =0,max=0;
HashMap<Character,Integer> map =new HashMap<Character,Integer>();
for(int i=0;i<s.length();i++){
char ch =s.charAt(i);
left = Math.max(left,map.containsKey(ch)?map.get(ch)+1:0);
max =Math.max(max,i-left+1);
map.put(ch,i);
}
return max;
}
编辑于 2018-01-21 10:26:55
回复(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)
/*
* 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 == null || s.length() < 1)
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+1-j);
}
return max;
}
/*
* Solution by me Runtime: 51 ms.Your runtime beats 80.99 % of java
* submissions. 思路：确定两个指针p1和p2,再new一个HashSet用来存储subString中的字符
* 循环：p2加1，如果HashSet不含有该字符，subString长度加1;如果含有该字符，把p1指向的字符删除，p1+1
*/
public int lengthOfLongestSubstring_1(String s) {
if (s == null || s.length() < 1)
return 0;
char[] arr = s.toCharArray();
Set<Character> set = new HashSet<Character>();
set.add(arr[0]);
int p1 = 0, p2 = 1;
int tempNum = 1, res = 1;
while (p2 < s.length()) {
while (set.contains(arr[p2])) {
set.remove(arr[p1++]);
tempNum--;
}
set.add(arr[p2++]);
tempNum++;
if (tempNum > res)
res = tempNum;
}
return res;
}
编辑于 2017-07-05 10:05:45
回复(0)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char,pair<int,int>> map;
if(s.length()==0) return 0;
int max=0x80000000,cur=0;
for(int i=0;i<s.length();i++){
if(map[s[i]].first==0){
map[s[i]].first++;
map[s[i]].second = i;
}
else{
if(cur<=map[s[i]].second){
int lens = i-cur;
cur = map[s[i]].second+1;
if(lens>max) max=lens;
map[s[i]].first++;
map[s[i]].second = i;
}
else{
map[s[i]].first++;
map[s[i]].second = i;
}
}
}
int tmp = (s.length() - cur);
if(tmp>max) max = tmp;
return max;
}
};
发表于 2016-11-24 21:05:43
回复(0)
/*
尺取法
*/
public class Solution {
public int lengthOfLongestSubstring(String s) {
int head = 0;
int index = 0;
int ans = 0;
int len = s.length();
boolean[] vis = new boolean[256];
for (boolean ele : vis) {
ele = false;
}
while (index < len) {
if (vis[s.charAt(index)] == false) {
vis[s.charAt(index)] = true;
index++;
} else {
ans = Math.max(ans, index - head);
while (s.charAt(head) != s.charAt(index)) {
vis[s.charAt(head)] = false;
head++;
}
head++;
index++;
}
}
return Math.max(ans,len - head);
}
}
发表于 2016-07-08 11:21:27
回复(0)
// 参考大神的思路，真是学到了！
import java.util.HashMap;
import java.util.Map;
public class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() == 0)
return 0;
// 滑动窗口法计算最长的不重复子串
// map记录字符的index
Map<Character, Integer> map = new HashMap<>();
int leftBound = 0;
int max = 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);
max = Math.max(max, i - leftBound + 1);
map.put(c, i);
}
return max;
}
}
发表于 2017-07-02 12:25:38
回复(0)
问题信息
难度：
101条回答
121收藏
26241浏览
通过挑战的用户
查看代码-
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号
