`

Longest Substring Without Repeating Characters

阅读更多
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

题目要求很简单,给定一个字符串,找到一个不包含重复元素的最长字符串。
我们可以用哈希表来处理,key中存放字符,value存放相应字符的下标,max记录不包含重复元素的最长字符串的长度。从第一个字符开始,如果当前字符在哈希表中,那么就更新遍历的开始位置,同时维护max;如果不在哈希表中,就将当前元素记录到哈希表中。代码如下:
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> hm = new HashMap<Character, Integer>();
        int max = 0;
        for(int i = 0; i < s.length(); i++) {
            if(!hm.containsKey(s.charAt(i))) {
                hm.put(s.charAt(i), i);
            } else {
                max = Math.max(max, hm.size());
                i = hm.get(s.charAt(i));
                hm.clear();
            }
        }
        return Math.max(max, hm.size());
    }
}


另外我们也可以用两个指针来处理这个题目。两个指针始终维护着一个不包含重复元素的字符串,不断的更新max来得到结果。代码如下:
public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if(s == null || s.length() == 0) return 0;
        int max = 1;
        int start = 0, end = 1;
        String current = s.substring(start, end);
        for(int i = 1; i < s.length(); i++) {
            if(current.indexOf(s.charAt(i)) >= 0 ) {
                max = Math.max(max, end - start);
                start += current.indexOf(s.charAt(i)) + 1;
            }
            end = end + 1;
            current = s.substring(start, end);
        }
        return Math.max(max, end - start);
    }
}
0
0
分享到:
评论

相关推荐

    LeetCode3 Longest Substring Without Repeating Characters

    Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...

    longest-substring-without-repeating-characters

    Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3. Given "bbbbb", the answer is "b", with...

    java-leetcode题解之Longest Substring Without Repeating

    今天我们要探讨的是LeetCode上的一个经典题目——“Longest Substring Without Repeating Characters(无重复字符的最长子串)”。 这个问题要求我们在给定的字符串中找到不含重复字符的最长子串的长度。一个子串是...

    js代码-3. Longest Substring Without Repeating Characters

    Longest Substring Without Repeating Characters" 描述的是一个经典的计算机编程问题,通常出现在面试或编程竞赛中。这个题目要求我们找到一个字符串中最长的子串,该子串中没有重复的字符。这是一个非常基础但又...

    Leetcode回文串拼接-leetcode_note:用于记录leetcode题目的解析

    Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring 6.ZigZag Conversion 7.Reverse Integer 8.String To Integer 9.Palindrome Number 10.String To Integer 11....

    程序员面试宝典LeetCode刷题手册

    3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17...

    Go 零基础2000题 从入门到精通

    说明 ⽬录 第⼀章 序章 关于 LeetCode 什么是 Cookbook 为什么会写这个开源书 关于书的封⾯ 关于作者 关于书中的代码 ⽬标读者 编程语⾔ ...3. Longest Substring Without Repeating Characters 4. ......

    js-leetcode题解3-longest-substring-without-repeating-characters.js

    2. 无重复字符的最长子串(Longest Substring Without Repeating Characters):这是一个在LeetCode上颇受欢迎的算法问题,旨在找出一个字符串中不包含重复字符的最长子串,并返回该子串的长度。 3. JavaScript (JS...

    leetcode分类-leetcode:leetcode问题的代码

    #3:Longest Substring Without Repeating Characters #5:Longest Palindromic Substring 链表 #2:Add Two Numbers 分而治之 #53:Maximum Subarray 队列/集 #3:Longest Substring Without Repeating Characters 优先...

    leetcodepython001-leetcode:https://leetcode.com/的解决方案

    Characters.cpp │  │  ├── 004 - Median of Two Sorted Arrays.cpp │  │  └── 005 - Longest Palindromic Substring.cpp │  └── python │  ├── 001 - Two Sum.py │  ├── 002 - Add Two...

    没有重复字符最长子串

    Given a string, find the length of the longest substring without repeating characters. Examples: Given "abcabcbb", the answer is "abc", which the length is 3.

    lrucacheleetcode-leetcode:leetcode

    Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 12. Integer to Roman 13. Roman to ...

    leetcode双人赛-LeetCode:力扣笔记

    Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 Longest Palindromic Substring 中等 回文 ZigZag Conversion 中等 矩阵 重要 Reverse Integer 简单 字串 String to Integer ...

    leetcodepython001-algorithm:leetcode问题(cpp、java、python),书籍破解_the_coding

    Characters4. Median of Two Sorted Arrays 004. Median of Two Sorted Arrays 005. Longest Palindromic Substring 006. ZigZag Conversion 007. Reverse Integer 008. String to Integer 009. Palindrome Number ...

    leetcode题库-LeetCode-Go:用GO回答LeetCode

    Repeating Characters 31.1% Medium 0004 Median of Two Sorted Arrays 30.7% Hard 0005 Longest Palindromic Substring 30.1% Medium 0006 ZigZag Conversion 37.5% Medium 0007 Reverse Integer 25.8% Easy 0008 ...

    javalruleetcode-leetcode-java:力码笔记

    Without Repeating Characters 5.Longest Palindromic Substring 20.Valid Parentheses 26.Remove Duplicates from Sorted Array 53.Maximum Subarray 70.Climbing Stairs 121.Best Time to Buy and Sell Stock 122....

    leetcode338-LeetCode:LeetCode刷题总结

    Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7.Reverse Integer 8.String to Integer (atoi) 9.Palindrome Number 10....

    javalruleetcode-LeetCode:LeetCode算法问题

    java lru leetcode Fighting for a job! 记录找工作期间搬运的题,全部使用Java实现,本人C++鶸 1 ...Longest Substring Without Repeating Characters LeetCode 13 Roman to Integer LeetCode 6 Zi

    dna匹配leetcode-leetcode:leetcode刷题

    Longest Substring Without Repeating Characters 哈希表 双指针 滑动窗口 Substring with Concatenation of All Words 哈希表 注意匹配方向 Valid Sudoku 数组 遍历 Sudoku Solver 深度优先遍历 回溯 先检查后修改 ...

Global site tag (gtag.js) - Google Analytics