编程练习:无重复字符的最长字串

题目LeetCode-无重复字符的最长字串

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

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

分析与实现

解法一
  • 分析
    这里面的难度在于,从i开始遍历,遇到相同字符后结束,记录长度。然后从i+1开始继续遍历
  • 实现(java)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    /**
    * 求不出现重复的最大字串的长度
    * @param s 源串
    * @return 长度值
    */
    public static int lengthOfLongestSubstring(String s) {

    if (s.length() < 2) {
    return s.length();
    }

    int maxLen = 0;
    List<Character> list = new ArrayList<>();
    for (int i = -1; i < s.length(); i++){
    list.clear(); // 每次清空map
    //list.add(s.charAt(i));
    for (int j = i+1; j < s.length(); j++) {
    Character c = s.charAt(j);
    if (!list.contains(c)){
    list.add(c);
    }else{
    // 说明存在了
    break;
    }
    }
    if (list.size() > maxLen) {
    maxLen = list.size();
    }
    }
    return maxLen;
    }

这里使用了list作为字串的存储,主要是便于判断字符的存在情况,用了两次for循环

这样做的确可以达到效果,但是时间复杂度很大,提交结果如下
解法一

解法二
  • 分析
    在每一次遍历到一个重复的字符时,其实在这之前的所有字符已经遍历,那么应该可以直接拿来用,所以这里分为三种情况:
  1. 情况1: 重复字符出现在子串的第一位;
  2. 情况2: 重复字符出现在子串的中间;
  3. 情况3: 重复字符出现在子串的最后;

关于这三种情况的处理详细见下面的代码中的注释分析:

  • 实现(java)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    if (s.length() < 2) {
    return s.length();
    }
    int maxLen = 0;
    List<Character> list = new ArrayList<>();
    for (int j = 0; j < s.length(); j++) {
    Character c = s.charAt(j);
    if (!list.contains(c)){
    list.add(c);
    }else{
    int index = list.indexOf(c); // 得到列表中该字符的下标
    /*
    1. 如果下标在最开始
    判断list的size和max的大小
    将第一个remove掉
    将新的字符加入list
    */
    if (index == 0){
    if (list.size() > maxLen) {
    maxLen = list.size();
    }
    list.remove(0);
    }
    /*
    2. 如果下标在最中间
    判断前面部分的长度是否大于当前的maxlen,如果是修改maxlen
    将index出之前(包括index出的字符)删除
    将j处的字符加入list
    */
    else if (index != 0 && index != (list.size() - 1)) {
    if (list.size() > maxLen) {
    maxLen = list.size();
    }
    for (int i = 0; i < index + 1; i++) {
    list.remove(0); // 移除index+1次;list的remove问题
    }
    }
    /*
    3. 如果下标在最最后
    判断size和maxlen的大小
    清除list中所有的元素
    将j处的字符加入
    */
    else {
    if (list.size() > maxLen) {
    maxLen = list.size();
    }
    list.clear();
    }
    list.add(c);
    }
    }

    if (list.size() > maxLen) { // 判断最后list中的字串长度
    maxLen = list.size();
    }
    return maxLen;

这样处理后,在时间复杂度上好了很多!

当然LeetCode上还有很多大佬的实现,时间复杂度还要低,但是思想都是重复利用遍历过序列

最后

此致,敬礼!

~~客官随意,我只是学习怎么配置打赏而已~~