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.
解法一:
遍历字符串,将每个字符放入到哈希表,利用哈希表来判断是否有重复的字符,如果有重复,记录哈希表的大小,并清空哈希表,然后继续从下一个位置开始查找。
(其实算法可以继续优化,即从相同的字符的索引的下一个位置继续查找)
程序如下:
public int lengthOfLongestSubstring(String s) { if(s == null || s.length()==0){ return 0; } Set<Character> charSet = new HashSet<Character>(); char[] ss = s.toCharArray(); charSet.add(ss[0]); int max = 1; for(int i=1;i<ss.length;i++){ for(int j=i;j<ss.length;j++){ if(!charSet.contains(ss[j])){ charSet.add(ss[j]); }else{ max = Math.max(max, charSet.size()); charSet.clear(); charSet.add(ss[i]); break; } } } return max; }
相关推荐
LeetCode 101:和你一起你轻松刷题(C++)
如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 "" 。 本测试数据是第265个测试用例,字符串长度100000,子串长度10000,正确的算法结果,最小覆盖子串长度应该为10742 下面是我的I7本地跑完的结果【网站...
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。 来源:力扣(LeetCode) 链接:...
找出字符串中最长的没有重复字符的子串,算法精巧,代码简洁
c语言 C语言_C语言编程基础之leetcode题解第5题最长回文子串
c++ c++_c++编程基础之leetcode题解第5题最长回文子串
python python_leetcode面试题解之无重复字符的最长子串
(1)如果当前遍历到的字符从未出现过,那么直接扩大右边界 (2)如果当前遍历到的字符出现过,则缩小窗口(左边索引向右移动),然后继续观察当前遍历到的字符 (3)
c# c#_Leetcode面试题解之第3题无重复字符的最长子串
c语言 C语言_C语言编程基础之leetcode题解第3题无重复字符的最长子串
c++ c++_c++编程基础之leetcode题解第3题无重复字符的最长子串
leetcode 答案最长子串 来自 leetcode.com 的问题。 描述: 给定一个字符串,找出没有重复字符的最长子字符串的长度。 示例 1: 输入:“abcabcbb” 输出:3 解释:答案是“abc”,长度为3。
这道题使用双指针(滑动窗口)+哈希表可破。 public int lengthOfLongestSubstring(String s) { if (s==null||s.equals("")) return 0; int start = 0; int end = 0;... char[] arr = s.toCharArray();...
c++ c++_c++编程基础之leetcode题解第76题最小覆盖子串
无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个排序数组的中位数 (40_Hard) LeetCode 5 : 最长回文子串 (251_Medium) LeetCode 6 : ZigZag 对话 (15_Medium) LeetCode 7 : 反转整数 (174_Easy) LeetCode 9 : ...
无重复字符的最长子串1
java面试 java面试_leetcode面试java编程题解之第3题无重复字符的最长子串_java题解
力扣3. 无重复字符的最长子串
leetcode思维导图-字符串