每日算法-无重复字符的最长子串

题目描述


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

示例1:

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

示例2:

输入:s = "bbbbb"
输出:1
解释:无重复字符的最长字串是"b",长度为1。

示例3:

输入:s = ""
输出:0

解答详情

思路:先理解清楚字符串的子串和子数组的概念,子串是连续的,子数组可以不连续;该题本人根据ASCII码,利用字符的ASCII码记录上一个字符出现的位置,若遇到相同的字符,则更新统计子串长度的起始位置,并记录相应无重复字符子串的长度,获取其最大值。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int len = s.length();//字符串长度
        if(len < 2) return len==1 ? 1 : 0;
        
        int[] preStrIdx = new int[128];//128位的ASCII码
        //利用字符的ASCII码记录上一个字符出现的位置
        for(int i = 0 ; i < 128 ; i++)preStrIdx[i] = -1;//初始化
        
        int res = 0;
        int start = 0;
        for(int i = 0 ; i < len ; i++){
            int idx = s.charAt(i);//字符对应的ASCII码
            start = Math.max(start,preStrIdx[idx]+1);//记录开始的位置
            res = Math.max(res,i-start+1);
            preStrIdx[idx] = i;//更新上一个字符的位置
        }
        return res;
    }
}


每日算法-无重复字符的最长子串

上一篇:java基础语法01 注释


下一篇:Halcon 自动对焦算法