小知识,大挑战!本文正在参与“程序员必备小知识”创作活动。
前言
- leetcode中算法第三题求无重复字符的最长子串,难度:中等;
- 再做之前有看过一些解决思路,有说用左右指针法计算最长长度,当时只看了一部分解决思路,没看完就自己动手去操作。
- 但是结果如果只用左右指针我根本就做不出来【笑哭】,附一张提交记录图:
过程
- 当时实在是搞不出来了【头大】,然后就想到之前有用hash表解决环状链表算法问题,就想着能否用hash表解决这题。
- 哈哈,最后通过不懈努力还是搞出来了。
/**
* @Author: ZRH
* @Date: 2021/10/19 17:06
*/
public class Test {
public static void main (String[] args) {
System.out.println(test("abcabcbb"));
System.out.println(test(""));
System.out.println(test(" "));
System.out.println(test("ua"));
System.out.println(test("aab"));
System.out.println(test("bb"));
System.out.println(test("pwwkew"));
System.out.println(test("abba"));
System.out.println(test("dvdf"));
}
private static int test (String s) {
// 获取当前字符串长度
final int length = s.length();
// 如果字符串长度小于等于1,直接返回即可
if (length <= 1) {
return length;
}
// 定义最大值和左偏移量
int max = 0, left = 0;
// 定义一个存放数据的hash表
Map<String, Integer> map = new HashMap<>(length * 2);
for (int i = 0; i < length; ) {
// 遍历每个字符
String a = String.valueOf(s.charAt(i));
// i++放这里,是为了计算当前字符前符合条件的长度
i++;
Integer b = map.get(a);
if (b != null) {
// 集合中存在字符,那就用其下标和左偏移量取较大值
left = Math.max(b, left);
}
// 当前字符下标-左偏移量后再取较大值
max = Math.max(i - left, max);
// 把元素放入hash中
map.put(a, i);
}
return max;
}
}
复制代码
- 代码中备注描述的也比较清晰,其时间复杂度 O(n)
最后
- 这题其实不算难,但是我也花费了较长时间才解决出来,只怪自己不够聪明吧;
- 勤能补拙,多刷刷题吧,虚心学习,共同进步 -_-
近期评论