字符串----3. 无重复字符的最长子串

傷城~ 2022-11-17 10:14 133阅读 0赞

【题目】  
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。  
【示例】  
输入: s = “abcabcbb”  
输出: 3  
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。  
【思路】  
双指针，集合记录每个字符是否出现过，  
记录左指针，起始指针，如果起始指针不等于0，清空集合中上一个位置元素  
集合不包含元素，添加到集合中，向右移动右指针  
第i 到第rk 是无重复子字符串。

【代码】

public int lengthOfLongestSubstring(String s) { 
    
            // 哈希集合，记录每个字符是否出现过
            Set<Character> occ = new HashSet<Character>();
            int n = s.length();
            // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
            int rk = -1, ans = 0;
            for (int i = 0; i < n; ++i) { 
                if (i != 0) { 
                    // 左指针向右移动一格，移除一个字符
                    occ.remove(s.charAt(i - 1));
                }
                while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) { 
                    // 不断地移动右指针
                    occ.add(s.charAt(rk + 1));
                    ++rk;
                }
                // 第 i 到 rk 个字符是一个极长的无重复字符子串
                ans = Math.max(ans, rk - i + 1);
            }
            return ans;
        }

发表评论取消回复

表情：

评论列表（有 0 条评论，133人围观）

还没有评论，来说两句吧...

相关阅读

相关 3.无重复字符的最长子串

前言撸题 -------------------- 题：给定一个字符串，请你找出其中不含有重复字符串的，最长子串的长度。实例1：入: s =

浅浅的花香味﹌/ 2023年01月06日 01:15/ 0 赞/ 143 阅读

相关 3.无重复字符的最长子串

前言撸题 -------------------- 题：给定一个字符串，请你找出其中不含有重复字符串的，最长子串的长度。实例1：入: s =

梦里梦外;/ 2022年11月19日 12:44/ 0 赞/ 156 阅读

相关字符串----3. 无重复字符的最长子串

【题目】给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。【示例】输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字

傷城~/ 2022年11月17日 10:14/ 0 赞/ 134 阅读

相关 3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是

我就是我/ 2022年10月14日 00:54/ 0 赞/ 140 阅读

相关 3. 无重复字符的最长子串

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

青旅半醒/ 2022年10月07日 06:51/ 0 赞/ 128 阅读

相关 3. 无重复字符的最长子串

[https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/][https

小鱼儿/ 2022年09月08日 03:56/ 0 赞/ 156 阅读

相关 3. 无重复字符的最长子串

给定一个字符串，找出不含有重复字符的最长子串的长度。示例：给定 `"abcabcbb"` ，没有重复字符的最长子串是 `"abc"` ，那么长度就是3。给定 `"b

柔情只为你懂/ 2022年05月21日 09:28/ 0 赞/ 189 阅读

相关 3. 无重复字符的最长子串

package com.cheng.leetcode; import java.util.HashMap; import java.util.

曾经终败给现在/ 2021年09月21日 14:28/ 0 赞/ 316 阅读

相关 3. 无重复字符的最长子串

3. 无重复字符的最长子串给定一个字符串，找出不含有重复字符的最长子串的长度。示例 1: 输入: "abcabcbb"

小鱼儿/ 2021年09月16日 16:48/ 0 赞/ 290 阅读

相关 3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的最长子串的长度。示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc

迈不过友情╰/ 2021年06月22日 15:38/ 0 赞/ 393 阅读