[数据结构与算法] leetCode第3题（找出字符串中不含有重复字符的最长子串的长度）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> leetCode第3题（找出字符串中不含有重复字符的最长子串的长度） -> 正文阅读

[数据结构与算法]leetCode第3题（找出字符串中不含有重复字符的最长子串的长度）

作者:token keyword

一、题目

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

示例1
输入: str=“abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是"abc",所以其长度为3

示例2
输入: str=“bbbbb”
输出: 1
解释：因为无重复字符的最长子串是"b",所以其长度为1

示例3
输入: str=“pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是"wke",所以其长度为3

示例4
输入: str=""
输出: 0

二、题目代码解析

package com.xz.leetcode.day3;

import java.util.HashSet;
import java.util.Set;

/**
 * @description: 给定一个字符串str，请你找出其中不含有重复字符的最长子串的长度
 *
 *              示例1
 *              输入: str="abcabcbb"
 *              输出: 3
 *              解释: 因为无重复字符的最长子串是"abc",所以其长度为3
 *
 *              示例2
 *              输入: str="bbbbb"
 *              输出: 1
 *              解释：因为无重复字符的最长子串是"b",所以其长度为1
 *
 *              示例3
 *              输入: str="pwwkew"
 *              输出: 3
 *              解释: 因为无重复字符的最长子串是"wke",所以其长度为3
 *
 *              示例4
 *              输入: str=""
 *              输出: 0
 * @author: xz
 * @create: 2021-07-27 22:11
 */
public class Demo {
    public static void main(String[] args) {
        String str="abcabcbb";
        int length=lengthOfLongestSubString(str);
        System.out.println("不含有重复字符的最长子串的长度: "+length);
    }

    public static int lengthOfLongestSubString(String str){
        //定义一个哈希集合，记录每个字符是否出现过
        Set<Character> set =new HashSet<>();
        //右指针的初始值为0，相当于我们在字符串的左边界第一个字符
        int rk =0;
        //最长子串的长度，初始值为0
        int ans=0;
        for(int i=0;i<str.length();++i){
            if(i != 0){
                //左指针向右移动一格，移除一个字符
                set.remove(str.charAt(i-1));
            }
            //不断的移动右指针
            while(rk < str.length() && !set.contains(str.charAt(rk))){
                //添加到set集合中
                set.add(str.charAt(rk));
                ++rk;
            }
            //计算最大值
            ans=Math.max(ans,rk-i);
        }
        return ans;

    }
}