美文网首页
字符串中无重复字符的最长子串

字符串中无重复字符的最长子串

作者: peter_ffec | 来源:发表于2021-08-15 18:12 被阅读0次

hot 100 meddium

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

见原题:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

解题思路(双指针,滑动窗口)

过程:

  1. 用set来进行字符去重
  2. 类似动态规划要记录上一次比较的状态
    1. 从当前尾指针位置开始遍历字符串,如果set中一直没有进入set,尾指针后移动;记录当前的最大值max和头尾指针之间的元素个数比较大小
    2. 如果遇到set中有的字符,跳出这层循环,头指针往右移动一个位置,尾指针不变,set中去掉第一个内容,继续判断尾指针指向字符是不是在set中,返回1.1

代码:

        int left=0;
        int right=-1;
        int len=s.length();
        int max =0;
        Set<Character> charSets= new HashSet<>();
        for(left=0;left<len;left++){
            if(left!=0)
                charSets.remove(s.charAt(left-1));  //删除头指针指向的set中的值
            while(right+1<len && !charSets.contains(s.charAt(right+1))){
                charSets.add(s.charAt(right+1));
                right++;  //尾指针满足条件右移动
            }
            max=Math.max(max,right-left+1);  //此处遇到重复字符时,最大的子串长度
        }
        return max;

难度系数:四颗星

相关文章

  • 【算法】字符串和数组操作01

    1、无重复字符的最长子串 给定一个字符串,请你找出其中不含有重复字符的 **最长子串 **的长度。 示例: 2、最...

  • 【leetcode-字符串】无重复字符的最长子串

    【leetcode-字符串】无重复字符的最长子串 给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。...

  • Longest Substring with At Most T

    Hard, Array/String 给定字符串,寻找最多包含两个重复字符的最长子字符串。P.S. 无重复字符串进...

  • 无重复字符的最长子串

    无重复字符的最长子串 给定一个字符串,找出不含有重复字符的最长子串的长度。 遍历字符串中的每一个元素。借助一个辅助...

  • LeetCode 3. Longest Substring Wi

    题目 给定一个字符串,请找出其中无重复字符的最长子字符串。 样例例如,在"abcabcbb"中,其无重复字符的最长...

  • LeetCode 3 [Longest Substring Wi

    原题 给定一个字符串,请找出其中无重复字符的最长子字符串。 样例例如,在"abcabcbb"中,其无重复字符的最长...

  • [Leetcode] 3. 无重复字符的最长子串

    3. 无重复字符的最长子串 来源: 3. 无重复字符的最长子串 1. 解题思路 滑动窗口寻找最大字符串 2. 代码

  • 子串问题(滑动窗口)

    1.无重复字符的最长子串(3 - 中/剑指48) 题目描述:给定一个字符串,请你找出其中不含有重复字符的 最长子串...

  • 算法练习二

    无重复字符的最长子串 给定一个字符串,找出不含有重复字符的最长子串的长度。示例:给定 "abcabcbb" ,没有...

  • 无重复字符的最长子串

    无重复字符的最长子串 给定一个字符串,找出不含有重复字符的最长子串的长度。 示例: 给定"abcabcbb",没有...

网友评论

      本文标题:字符串中无重复字符的最长子串

      本文链接:https://www.haomeiwen.com/subject/iwwubltx.html