力扣3:无重复字符最长子串(哈希表)

崩天的勾玉
崩天的勾玉
崩天的勾玉
65
文章
4
评论
2021年5月25日23:12:46
评论
15 493字

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

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character,Integer> map = new HashMap<>();
        int index = 0,ans = 0;
        for(int i = 0;i<s.length();i++){
            char c = s.charAt(i);
            if(map.containsKey(c)){
                index = Math.max(map.get(c),index);
            }
            ans = Math.max(ans,i-index+1);
            map.put(c,i+1);
        }
        return ans;
    }
}

查询可以转化成哈希表,速度够快。

当前字符为key,value为位数。(不用下标是因为位数比下标大1不用考虑空字符串要返回1的问题)

如果表中有了相同的字符,那就迭代一下较大的位数,往后延伸。

i-index+1是位数之差+1也就是字符数,也需要进行较大值的迭代。

最后返回最大的。

发表评论

匿名网友