LeetCode第3题无重复字符的最长子串

继续打卡算法题，今天学习的是第LeetCode的第3题无重复字符的最长子串，这道题目是道中等题。算法题的一些解题思路和技巧真的非常巧妙，每天看一看算法题和解题思路，我相信对编码能力有一些帮助。

分析一波题目

这道题目就是一个比较有意思的题目，从一个字符串找不相同的最长的子字符。

题目里的关键信息： 1、注意是找最长的，因此我们肯定需要把最长的记录下来。题目只要求返回长度，因此使用一个整形变量就可以了。 2、不含重复字符，这个信息很关键，我们可以以每个字符开头开始遍历，通过hashset记录遍历过的元素，不断的累计，如果遇到重复的，说明已经找到了以这个元素开头的最大子串，记录下来，需要重写找另外一个元素开头的子串。

编码实现

class Solution {
   
   
    //整体思路，只要遇到一个重复的字符，就抛弃一个元素，重新计算最长子串
    public int lengthOfLongestSubstring(String s) {
   
   
            //集合存储不重复的子元素
            Set<Character> set = new HashSet<>();
            int maxlen = 0;
            int start = 0;
            for(int i=0; i<s.length(); i++) {
   
   
                //i之前，s.charAt(i)字符出现过，重新开始一个位置
                if(set.contains(s.charAt(i))) {
   
   
                    //清空不重复元素队列，重新计算不重复字符队列，这样做的原因：因为有重复的元素，那么在i之前都找不到最长子串了
                    //因此抛弃一个元素，重新找最长子串
                    i = start;
                    start++;
                    set.clear();
                } else {
   
   
                    //字符没出现过，加入不重复字符队列
                    set.add(s.charAt(i));
                }
                //最大的子串数量，记录下来
                if(set.size() > maxlen) {
   
   
                    maxlen = set.size();
                }

            }
            return maxlen;
    }
}

总结

这个题目一开始看着只能想到使用暴力解法，深入思考一下使用HashMap可以减少循环，遇到有没有重复元素的情况，可以考虑看下使用HashMap结构能不能降低复杂度。