0%

leetcode之旅-03-无重复字符的最长子串

Posted on Edited on In

1. 题目描述

题目描述

  • 概述：

2. 我的解法

1
class Solution {
2
    public int lengthOfLongestSubstring(String s) {
3
        if(s==null||s.equals("")) return 0;
4
        int Max=1;
5
        for(int i=0;i<s.length();i++)
6
        {
7
            for(int j=i+1;j<s.length();j++)
8
            {
9
if(s.substring(i,j).indexOf(String.valueOf(s.charAt(j)))==-1) 
10
                    Max=(Max>=(j-i+1))?Max:(j-i)+1;
11
                else break;
12
            }
13
        }
14
        return Max;
15
    }
16
}

时间复杂度：最坏到达O($n^2$)

3 解法二

  1. 我的解法存在一点问题：每次第二层循环结束时j都回到i+1的位置。
  2. 改进：由于之前的探索可知i-j之间存在与j位重复的字符，那么下一次循环的时候，j的位置可以固定不动，移动i至重复字符的下一位即可。
1
class Solution {
2
    public int lengthOfLongestSubstring(String s) {
3
        if(s==null||s.equals("")) return 0;
4
        int Max=1 , n = s.length() , sub = 0;
5
        for(int i=0,j=i+1 ; i<n&&j<n ;j++)
6
        {//每次都探索新的j
7
            int reindex=s.substring(i,j).indexOf(s.charAt(j));
8
            if(reindex == -1) 
9
                Max=(Max>=(j-i+1))?Max:j-i+1;
10
            else
11
            {
12
                i = sub+reindex +1;//移到重复位置的下一位
13
                sub = i;//寻找i在s中移动的位置，reindex只是子字符串总的位置
14
            }
15
        }
16
        return Max;
17
    }
18
}
  • 时间复杂度：O(n)

4 解法四

巧用hashmap。
采用i跳跃的方式，维护hashmap中的键值对。

  • 如果没有重复字符，则向map中加入新的j位置的字符，value值为如果发生重复，i需要跳转到的位置。其实也是不断更新对应字符的下一次跳转位置。
  • 如果发生重复，i跳转的规则是取当前位置和重复字符所在位置的下一个位置的最大值。因为map在去字串时没有删除之前的字符。这样做的目的是为了防止，当前重复的字符其实并没有包含在当前字串中，而是之前遗留的字符，防止i倒退。
    1
    public class Solution {
    2
        public int lengthOfLongestSubstring(String s) {
    3
            int n = s.length(), ans = 0;
    4
            Map<Character, Integer> map = new HashMap<>(); 
    5
            for (int j = 0, i = 0; j < n; j++) {
    6
                if (map.containsKey(s.charAt(j))) {
    7
                    i = Math.max(map.get(s.charAt(j)), i); //采用i跳跃
    8
                }
    9
                ans = Math.max(ans, j - i + 1);
    10
                map.put(s.charAt(j), j + 1);//下标 + 1 代表 i 要移动的下个位置
    11
            }
    12
            return ans;
    13
        }
    14
    }
  • 时间复杂度：O(n)
  • 空间复杂度：O(m)

更多解法，看题解

5. 扩展

5.1 Java - String valueOf() Method

题目描述 Method .png)
这个方法的作用就是将其他的类型转化为string的形式，包括将boolean char char[] doubel float int long Object

5.2 Java String indexOf()

返回输入文本的在string中的下标

  1. 输入一个char，输出该char在字符串中对应的下标
    题目描述1.png)
  2. 输入插入和你strt值，从字符串的strt位置开始查找输入的字符第一次出现的下标
    题目描述2.png)
  3. 可以查找substring 对应的下标的方法
    题目描述3.png)
  4. 可以从指定位置开始查找substring，输出下标
    题目描述4.png)