欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode3 无重复字符的最长子串

程序员文章站 2022-04-04 09:59:43
...

3. 无重复字符的最长子串 - 力扣(LeetCode)

题目 LeetCode3:无重复的最长子串
LeetCode3 无重复字符的最长子串
解法:
(1)线性法:
LeetCode3 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
            // 定义一个哈希集合 set,初始化结果 max 为 0
        Set<Character> set = new HashSet<>();
        int max=0;

        /* 用快慢指针 i 和 j 扫描一遍字符串,如果快指针所指向的字符已经出现在哈希集合里,
            不断地尝试将慢指针所指向的字符从哈希集合里删除
        */
        for(int i=0,j=0; j<s.length();j++ ){
            while(set.contains(s.charAt(j))){
                set.remove(s.charAt(i));
                i++;
            }
            // 当快指针的字符加入到哈希集合后,更新一下结果 max
            set.add(s.charAt(j));
            max = Math.max(max,set.size());
        }
        return  max;
    }
}

改进后的解法:
LeetCode3 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
         Map<Character, Integer> map = new HashMap<>();
        int max = 0;

        // 用快慢指针 i 和 j 扫描一遍字符串,若快指针所对应的字符已经出现过,则慢指针跳跃
        for( int i =0,j=0;j<s.length();j++){
            if(map.containsKey(s.charAt(j))){
                i = Math.max(i,map.get(s.charAt(j)) +1);
            }
            
            map.put(s.charAt(j),j);
            max = Math.max(max,j-i+1);
            
        }
        return max;

    }
}