LeetCode3 无重复字符的最长子串 题目信息

发表于

这是我参与11月更文挑战的第15天，活动详情查看：2021最后一次更文挑战」 @TOC

题目信息

1
2
c复制代码给定一个字符串 s ，
请你找出其中不含有重复字符的 最长子串 的长度。

示例1：

1
2
3
java复制代码输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例2：

1
2
3
java复制代码输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例3：

1
2
3
4
java复制代码输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例4：

1
2
java复制代码输入: s = ""
输出: 0

解题思路：双指针扫描

假设下面的字符串是题目给出的字符串。

1
2
3
4
5
6
7
8
c复制代码定义结果res代表最长子串的长度。
定义双指针i，j起初都在0号下标位置，遍历整个字符串，
接着定义哈希表map，键值对为Character,Integer。
表示当前字符出现的次数。每次遇到一个字符，就将它放到map中，
直到该字符在map中的value值大于1，
这时候就说明存在重复的字符了。
接着将当前j下标的字符放进map中，value值为当前j下标的value值减1；
接着j++；更新res。最后返回res。

在这里插入图片描述

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
java复制代码    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> hashMap=new HashMap<> ();
        int res=0;
        for(int i=0, j=0; i<s.length ();i++){
            hashMap.put (s.charAt (i), hashMap.getOrDefault (s.charAt (i), 0)+1);
            while (hashMap.get (s.charAt (i))>1){
                hashMap.put (s.charAt (j), hashMap.get (s.charAt (j))-1);
                j++;
            }
            res=Math.max (res,i-j+1);
        }
        return  res;
    }

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%