无重复字符的最长子串

发表于 分类于 ， ， 阅读次数：

题目描述

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

示例 1:

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的题解

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int max=0;
        int cnt=0;
        int a=0,b=0;
        for(int i=0;i<s.length();i++)
        {
            a=i;
            cnt=0;
            for(int k=i;k<s.length();k++)
            {
                b=k;
                if(k>i&&s.substring(a,b).contains(s.charAt(k)+""))
                {
                    cnt=1;
                    a=b;
                }
                else
                {
                    cnt++;
                }
                max=Math.max(max,cnt);
            }
            if(max>=s.length()-i)
            {
                break;
            }
        }
        return max;
    }
}

问就是直接暴力,不过很显然大数据不行！！！

大神题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }
}

作者：guanpengchn
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solution/hua-jie-suan-fa-3-wu-zhong-fu-zi-fu-de-zui-chang-z/

这种解法的主要思想是用hashmap记录串中每个字母出现的最后一个位置，当出现重复的字母时就更新start的值，下次不重复的串的长度就从start开始记录，一开始start记录为零，要小心算法中加一减一的关系。还有一种优化的算法，将哈希表改为数组来存储。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        int[] index = new int[128];
        for (int j = 0, i = 0; j < n; j++) {
            char c = s.charAt(j);

            //i作为下标，如果是不重复的，那么i一定不会增长
            i = Math.max(index[c], i);
            //然后放进去，下次有重复的对比就好有值
            index[c] = j + 1;
            //ans作为长度，每次都比较一下长度被改变，直到遇到重复，不然每次长度加一
            ans = Math.max(ans, j - i + 1);
        }
        return ans;
    }
}

力扣官方推荐答案。

该算法用数组下标作为key,里面的值存储作为value,进一步提升了程序的效率。