这是悦乐书的第341次更新,第365篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Medium级别的第2题Longest Substring Without Repeating Characters(顺位题号是3)。给定一个字符串,找到最长无重复字符子字符串的长度。例如:

输入:“abcabcbb”
输出:3
说明:答案是“abc”,长度为3。

输入:“bbbbb”
输出:1
说明:答案是“b”,长度为1。

输入:“pwwkew”
输出:3
说明:答案是“wke”,长度为3。请注意,答案必须是子字符串,“pwke”是子序列而不是子字符串。

02 第一种解法

暴力解法,使用双指针HashSet

每次选取一个字符,从该字符开始往后遍历,存入HashSet中去,借助HashSet来判断是否重复出现,如果遇到重复字符,就结束循环,计算起始索引的长度,然后将HashSet清空,继续循环,再从第二个字符开始遍历,直到处理完所有字符。

此解法的时间复杂度是O(N^2),最坏情况下时间复杂度是O(N^3),因为HashSet的contains方法;空间复杂度是O(N)

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<Character>();
    int n = s.length(), left = 0, right = 0;
    int result = 0;
    for (int i=0; i<n; i++) {
        left = i;
        right = i;
        while (right < n && !set.contains(s.charAt(right))) {
            set.add(s.charAt(right));
            right++;
        }
        result = Math.max(result, right-left);
        set.clear();
    }
    return result;
}


03 第二种解法

针对第一种解法,我们还可以将HashSet换成数组,用数组来判断字符是否重复出现,其他思路一样。

public int lengthOfLongestSubstring2(String s) {
    int[] set = new int[256];
    int n = s.length(), left = 0, right = 0;
    int result = 0;
    for (int i=0; i<n; i++) {
        left = i;
        right = i;
        while (right < n && ++set[s.charAt(right)] < 2) {
            right++;
        }
        result = Math.max(result, right-left);
        // 将数组元素值全部重置为0
        Arrays.fill(set, 0);
    }
    return result;
}


04 第三种解法

滑动窗口算法。

此解法和上面的第一种解法有点类似,使用两个变量,一左一右,像窗口一样滑动,遇到重复值时,就将左边的一个字符从HashSet中移除,直到遍历完所有字符。

此解法的时间复杂度是O(N),最坏情况下时间复杂度是O(N^2),因为HashSetcontains方法;空间复杂度是O(N)

public int lengthOfLongestSubstring3(String s) {
    Set<Character> set = new HashSet<Character>();
    int n = s.length(), left = 0, right = 0;
    int result = 0;
    while (left < n && right < n) {
        if (!set.contains(s.charAt(right))) {
            set.add(s.charAt(right));
            right++;
            result = Math.max(result, right-left);
        } else {
            set.remove(s.charAt(left));
            left++;
        }
    }
    return result;
}


05 第四种解法

使用索引值来判断,同时将HashSet换成256大小的数组。

public int lengthOfLongestSubstring4(String s) {
    int[] set = new int[256];
    int n = s.length(), i = 0, j = 0;
    int result = 0;
    while (i < n && j < n) {
        i = Math.max(set[s.charAt(j)], i);
        result = Math.max(result, j-i+1);
        set[s.charAt(j)] = j+1;
        j++;
    }
    return result;
}


06 小结

算法专题目前已连续日更超过六个月,算法题文章210+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,好看、留言、转发就是对我最大的回报和支持!

内容来源于网络如有侵权请私信删除
你还没有登录,请先登录注册
  • 还没有人评论,欢迎说说您的想法!