X

LEETCODE 3. Longest Substring Without Repeating Characters

无重复字符的最长子串

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

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
      请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=3

解题思路分析:

本题是一道双指针题目,类似的题目在Leetcode中有很多,比如 LEETCODE 340. Longest Substring with At Most K Distinct Characters 解题思路分析。那一题也是求最大连续无重复字串长度,但是不重复的字符个数最多只能有k个。而本题没有k的限制,只要只要字串中没有重复字符即可。

首先我们定义2个指针,左指针和右指针初始位置都在0,然后再定义一个Map,来存储当前区间(左指针到右指针范围)内每种字符出现的次数。开始先移动右指针,查看当前右指针指向的字符,如果该字符之前出现过0次,说明当前字符是首次出现,即当前区间内不存在重复字符,此时区间长度为一个合理解,用当前合理解更新全局最大合理区间长度。反之,如果当前字符之前已经出现过1次,那么说明当前出现了重复字符,此时区间为不合理区间,这时开始移动左指针,查看左指针指向的字符,如果该字符之前出现过1次,左指针划过该字符下标,该字符从区间内被移出,区间内出现次数减一(变为0),继续移动左指针,如果当前字符出现次数为2,说明当前字符原先是重复字符,移除该字符后,该字符变成唯一,此时区间又变为合理区间,结束移动左指针,返回继续移动右指针。直到右指针到达字符串尾部,结束循环。

实现代码:

public int lengthOfLongestSubstring(String s) {
    // 为了提高效率,将字符串转为字符数组
    char[] arr = s.toCharArray();
    // 记录区间内每种字符出现个数
    Map<Character,Integer> map = new HashMap<>();
    // 左右2指针
    int left=0,right=0;
    // 返回结果
    int res=0;
    // 循环右指针
    while(right<s.length()){
        // 查看当前右指针指向字符在区间内出现个数
        int countRight = map.getOrDefault(arr[right], 0);
        // 将个数加一保存至map
        map.put(arr[right], countRight+1);
        // 如果之前该字符出现个数为0,
        // 说明当前该字符为首次出现,区间内不包含重复字符
        // 当前区间为合理区间
        if(countRight==0) {
            // 更新全局合理区间最大长度
            res=Math.max(res, right-left+1);
        } else{ // 如果当前字符在区间内出现过
            while(left<=right){
                // 移动左指针,查看左指针指向的字符个数
                int countLeft = map.get(arr[left]);
                // 将字符个数减一保存至map
                map.put(arr[left], countLeft-1);
                // 移动左指针
                left++;
                // 如果该字符原先出现过2次,即重复字符,
                // 移除一个该字符后,该字符变为唯一,区间变为合理
                // 结束移动左指针,返回移动右指针
                if(countLeft==2) break;
            }                
        }
        right++;
    }
    return res;
}

本题解法执行时间为11ms。

Runtime: 11 ms, faster than 34.06% of Java online submissions for Longest Substring Without Repeating Characters.

Memory Usage: 46.6 MB, less than 5.20% of Java online submissions for Longest Substring Without Repeating Characters.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-3-longest-substring-without-repeating-characters/
Categories: leetcode
kwantong: