目录
刷题日期：下午7:13 2021年5月13日星期四
个人刷题记录，代码收集，来源皆为leetcode
经过多方讨论和请教，现在打算往Java方向发力
主要答题语言为Java
题目：
剑指 Offer 48. 最长不含重复字符的子字符串
难度中等203
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
s.length <= 40000
题目分析
乍一看这道题并不难，可能有自己没有考虑到的地方。
直观解答首先考虑边界输入为空的情况，然后直接遍历该字符串，每当有相等元素出现将res置1，否则res++，尝试实现
初始解答：
class Solution {
public int lengthOfLongestSubstring(String s) {
//边界条件
if(s.length() <= 0) return 0;
int res = 0,count = 0; //初始化结果，最短为1
for(int i = 0; i < s.length()-1; i++){
if(s.charAt(i) == s.charAt(i + 1)){
count = 1;
} else {
count++;
}
if(count > res) res = count;
}
return res;
}
}
输入"abcabcbb"
输出6
差别 预期结果 3
果然是想的简单了，没有读清楚题，在第四个位置a已经出现了，所以就得置1，所以还需要一个字符列表存放已经出现的结果，然后每次都查找一遍是否出现过。
学习方法一，思想很接近，就是不懂哈希集合的查找方法
class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0;//初始化结果，最短为1
Set<Character> set = new HashSet<>(); //哈希即的.contains方法
for(int l = 0, r = 0; r < s.length(); r++){ //遍历，有的入集，没有后推
char c = s.charAt(r); //当前字符
while(set.contains(c)){
set.remove(s.charAt(l++)); //重复则减一遍，顺便去掉重复元素
}
set.add(c);//不管以前有没有，全加进去
if(r - l + 1 > res) res = r - l + 1; //最长结果就是左右两边做差
}
return res;
}
}
执行结果：通过
显示详情 添加备注
执行用时：8 ms, 在所有 Java 提交中击败了53.02%的用户
内存消耗：38.4 MB, 在所有 Java 提交中击败了69.53%的用户
学习他人：
方法一:
mata川L5 （编辑过）2020-02-19 来字节和孙哥做兄弟，滑动窗口，用set维护一个不重复的窗口
class Solution {
public int lengthOfLongestSubstring(String s) {
int res = 0;
Set<Character> set = new HashSet<>();
for(int l = 0, r = 0; r < s.length(); r++) {
char c = s.charAt(r);
while(set.contains(c)) {
set.remove(s.charAt(l++));
}
set.add(c);
res = Math.max(res, r - l + 1);
}
return res;
}
}
方法二
热带雨林 2021-03-31 方法二
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s.isEmpty()) return 0;//如果字符串为空，返回0
if (s.length()==1) return 1;//如果字符串只有一个字符，返回1
int[] dp=new int[s.length()];//dp[j]用于存储以j为结尾的不重复字符串的长度
//由于这是一个动态规划算法，所以先初始化最小的最优解
dp[0]=1;
int max=0;
for (int j = 1; j < s.length(); j++) {//已经知道dp[0],这里直接从1索引开始
int i=j-1;//设置一个i,从j-1开始，向前遍历。如果找到一个与j相同的字符，那么就停止索引（i--,因此i停留在该字符的前一位）
while (i>=0&&s.charAt(i)!=s.charAt(j)){
i--;
}
if (dp[j-1]<j-i){//说明s[i]在最短字符串之外
dp[j]=dp[j-1]+1;
}
else if (dp[j-1]>=j-i){//说明s[i]在最短字符串之内
dp[j]=j-i;
}
max=Math.max(dp[j],max);
}
return max;
}
}
方法三：
K神：
方法一：动态规划 + 哈希表
作者：jyd
链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/mian-shi-ti-48-zui-chang-bu-han-zhong-fu-zi-fu-d-9/
来源：力扣（LeetCode）
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> dic = new HashMap<>();
int res = 0, tmp = 0;
for(int j = 0; j < s.length(); j++) {
int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
dic.put(s.charAt(j), j); // 更新哈希表
tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
}
return res;
}
}
方法二： 动态规划 + 线性遍历
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> dic = new HashMap<>();
int res = 0, tmp = 0;
for(int j = 0; j < s.length(); j++) {
int i = j - 1;
while(i >= 0 && s.charAt(i) != s.charAt(j)) i--; // 线性查找 i
tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
}
return res;
}
}
方法三：双指针 + 哈希表
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> dic = new HashMap<>();
int i = -1, res = 0;
for(int j = 0; j < s.length(); j++) {
if(dic.containsKey(s.charAt(j)))
i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
dic.put(s.charAt(j), j); // 哈希表记录
res = Math.max(res, j - i); // 更新结果
}
return res;
}
}
总结
以上就是本题的内容和学习过程了，因为题目的原因，肯定都需要一个容器来存放已经出现过的结果，相比之下方法一只存内容然后调用方法反而更容易理解和简单一些，K神的学习一下就好。
欢迎讨论，共同进步。