寻找没有重复字符的最长字串

没有重复字符的最长字串

Posted by LY on February 12, 2019

在这里小小推荐下我的个人博客

csdn:雷园的csdn博客

个人博客:雷园的个人博客

简书:雷园的简书

前言

  1. 时长不更新,小编的心里也是非常的难过,怪自己没有好的知识与大家分享。
  2. 最近准备把算法慢慢的捡起来,所以准备日更一道算法题目,难度自然是由简入难,所以同学们可以每天都来看看小编的更新。
  3. 日更时间定在每晚20:00,希望大家多多关注啦。

没有重复字符的最长子串

给定一个字符串,查找不重复字符的最长子字符串的长度。

Example 1:

输入: "abcabcbb"
输出: 3 
说明: 正确的字串是 "abc", 长度是3。 

Example 2:

输入: "bbbbb"
输出: 1
说明: 正确的字串是 "b", 长度是1.

Example 3:

输入: "pwwkew"
输出: 3
说明: 正确的字串是 "wke", 长度是3. 

解题思路

  1. 看到题目,我们可以了解到,我们需要的是没有重复字符的字符串,由此我想到了HashSet,我们可以利用它的特性来处理这道题目。
  2. 有了HashSet集合来存储数据,我们就可以非常简单验证重复,那后面就是通过简单的暴力求解,来寻找最长的没有重复的子串。
  3. 有了以上两点,我们把他们融合到一起,就可以实现寻找没有重复字符的最长子串。详见下方代码及注释:
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length(); // s为传入字符串,len为字符串总长度
        int max = 0; // 定义默认没有重复字符的最长子串长度为0
        // 遍历每一个字符
        for (int i = 0; i < s.length(); i++) {
            // 比较当前最大长度与剩余字符
            if (max < len - i) {
                HashSet<String> stringHashSet = new HashSet<>(); // 实例化一个hashSet用来存储字符
                // 从当前字符向后遍历
                for (int j = i; j < len; j++) {
                    // 向集合中添加元素并判断是否添加成功,若添加失败则表示字符重复并跳出当前循环。
                    if (!stringHashSet.add(s.charAt(j) + "")) {
                        break;
                    }
                }
                int setLen = stringHashSet.size(); // 定义一个集合长度
                // 判断集合长度是否大于当前答案,如果满足就更新答案值。
                if (setLen > max)
                    max = setLen;
            } else break;
        }
        return max;
    }
}

最后说两句

  1. 所有的题目都有很多种解法,我的一定不是最好的,甚至可以说是比较低端的解法,希望大牛们多多指教!!!
  2. 如果朋友们对算法、编程有很大兴趣的话,可以私信我,大家一同探讨;相互学习、共同进步。
  3. 朋友们如果对这道题目有更好的解法,希望可以在评论中指出,让大家一起讨论学习。
  4. 最后感谢大家的阅读以及关注,谢谢大家!!!