LeetCode3.无重复字符的最长子串-Toy模板网

这篇具有很好参考价值的文章主要介绍了LeetCode3.无重复字符的最长子串。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

LeetCode3.无重复字符的最长子串,leetcode,算法,java,leetcode

虽然是一道中等题，但我5分钟就写完了，而且是看完题就知道怎么写，这一看就知道双指针，一个左一个右，右指针往后移如果没有重复的长度+1；如果有重复的，左指针往右移，那如何判断重复呢，这多简单，Hashset的congtains方法啊，所以一下子就写出来了，但是效率确实不高，只击败了百分之九，以下是我的代码：

class Solution {
    public int lengthOfLongestSubstring(String s) {
         int ans =0;
         int n = s.length();
         for(int i = 0;i<n;i++){
             HashSet<Character> set = new HashSet<>();
             set.add(s.charAt(i));
             int count = 1;
             for(int j = i+1;j<n;j++){
                 if(!set.contains(s.charAt(j))){
                     set.add(s.charAt(j));
                     count++;
                 }else{
                     break;
                 }
             }
             ans = Math.max(ans, count);
         }
         return ans;
    }
}

看了一下题解，题解就更优了一点，他的右指针只需要往右移动一遍即可。

字符串abcabcbb为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。

LeetCode3.无重复字符的最长子串,leetcode,算法,java,leetcode

可以发现最长字串起始位置递增的时候，结束位置也在递增，这是因为：假如我们选第k个字符为起始位置，第r个字符是它的结束位置，那么下次选择第k+1个字符为起始位置的时候，第k+1到r一定是不重复的，而且由于少了第k个字符，那么结束位置一定大于等于r，所以右指针不需要回去，

但是题解和左右指针又不完全一样，它用的是滑动窗口，就是用一个Hashset作为一个滑动窗口，里面装了左右指针之间的这一段字符，如果左指针右移，那么hashset就要删掉左指针之前指的那个字符；如果右指针右移，那么hashset就要加入右指针新指的字符了，子串的长度就是右指针-左指针+1，以下是题解代码：文章来源地址https://www.toymoban.com/news/detail-671947.html

class Solution {
    public int lengthOfLongestSubstring(String s) {
         int ans =0;
         int n = s.length();
         for(int i = 0;i<n;i++){
             HashSet<Character> set = new HashSet<>();
             set.add(s.charAt(i));
             int count = 1;
             for(int j = i+1;j<n;j++){
                 if(!set.contains(s.charAt(j))){
                     set.add(s.charAt(j));
                     count++;
                 }else{
                     break;
                 }
             }
             ans = Math.max(ans, count);
         }
         return ans;
    }
}

到了这里，关于LeetCode3.无重复字符的最长子串的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！