目录
原题:
力扣地址:
我们直接看题解吧:
解题方法:
难度分析:
难度算中下吧,这个总体不算很难,而且滑动窗口,以及哈希都比较常见
审题目+事例+提示:
解题思路(滑动窗口+哈希):
代码实现:
原题:
1.题目:最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串,计算该最长子字符串的长度。假设字符串中值包含‘a’-‘z’的字符。例如,在字符串“arabcacfr”中,最长的不含重复字符的子字符串是“acfr”,长度为4。
力扣地址:
LCR 167. 招式拆解 I - 力扣(LeetCode)
难度:中等
今天刷无重复最长字符串(最长无重复子字符串),大家有兴趣可以点上看看题目要求,试着做一下。
我们直接看题解吧:
解题方法:
这道题比较明显的看出适合用滑动窗口(双指针)题目,同时+哈希(效率更高)
难度分析:
难度算中下吧,这个总体不算很难,而且滑动窗口,以及哈希都比较常见
审题目+事例+提示:
解题思路(滑动窗口+哈希):
1、定义双指针f=0,s=-1,从字符串的同一侧出发进行遍历
2、f首先遍历:
·若与前面无重复,则放入哈希表,更新最长字符串长度,接着遍历下一位
· 若当前出现与之前的字符重复,则f访问下一位,s访问前面重复字符的下一位
·重复上述过程。
3、返回对应的字符串长度
代码实现:
class Solution {
public int dismantlingAction(String arr) {
//创建哈希表,key装字符元素,value装对应的下标
Map<Character, Integer> dic = new HashMap<>();
//res装相应字符串最大长度
int s = -1, res = 0, len = arr.length();
for(int f = 0; f < len; f++) {
if (dic.containsKey(arr.charAt(j)))
//与前面字符出现重复,比较下标大小,更新s
s = Math.max(s, dic.get(arr.charAt(f))); // 更新左指针 s
// 当存在重复时更新重复元素哈希表记录的下标,当无重复时放入无重复元素及下标
dic.put(arr.charAt(f), f);
res = Math.max(res, f - s); // 更新最长字符串长度结果
}
return res;
}
}