Fork me on GitHub

无重复字符的最长子串

封面

算法题解:无重复字符的最长子串

leetcode地址: leetcode

题目: 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

1
2
3
4
5
示例 1:

输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

解法1:暴力求解

  • 思路:遍历字符串,以每一个字符作为子串的起始字符,向后查找直到遇到和该字符相同的字符,记录长度,依次执行直到找到最长长度。

  • 题解如下:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
     public int maxIndexStrLength(String s) {
    int maxLength = 0;
    for (int index = 0; index < s.length(); index++) {

    int length = 1;
    int i = index + 1;
    for (; ; ) {
    if (i >= s.length()) {
    break;
    }
    String ts = s.substring(index, i);
    char c = s.charAt(i);
    if (ts.contains(c + "")) {
    break;
    }
    length++;
    i++;
    }
    maxLength = maxLength > length ? maxLength : length;
    }
    return maxLength;
    }

解法2:滑动窗口法

  • 思路:在使用暴力解法时我们会发现实际上对于无重复子串来讲,我们产生了一些冗余的判断操作。例如对于串sdabcabcbb,判断了子串sdabc之后,当后面再出现字符a,那么重复字符之前的串直接舍弃就好。即直接从bca…开始判断即可。这样可以减少大量的不必要的判断与计算操作。
  • 题解如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int maxIndexStrLength(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;
}

总结

  • 滑动窗口法的思路可以用来解决很多字符串相关的问题
陈年风楼 wechat
本不想放微信的,如果有转账的需求,请加我好友~哈哈