无重复字符的最长子串
创建时间:
字数:508
阅读:
无重复字符的最长子串
题目:
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是子串的长度,”pwke” 是一个子序列,不是子串。
解法一:C语言
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| int lengthOfLongestSubstring(char * s){ int start = 0, end = 0, maxlen = 0; char map[256] = {0}; map[(int)*(s+start)] = 1; while( *(s+end) != 0 ) { maxlen = maxlen>(end-start+1)?maxlen:(end-start+1); ++end; while( 0 != map[ (int)*(s+end) ] ) { map[ (int)*(s+start) ] = 0; ++start; } map[(int)*(s+end)] = 1; } return maxlen; }
|
解法二:Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| class Solution { public int lengthOfLongestSubstring(String s) { if (s.length()==0) return 0; HashMap<Character, Integer> map = new HashMap<Character, Integer>(); int max = 0; int left = 0; for(int i = 0; i < s.length(); i ++){ if(map.containsKey(s.charAt(i))){ left = Math.max(left,map.get(s.charAt(i)) + 1); } map.put(s.charAt(i),i); max = Math.max(max,i-left+1); } return max; } }
|
解法三:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; Map<Character, Integer> map = new HashMap<>(); for (int end = 0, start = 0; end < n; end++) { char alpha = s.charAt(end); if (map.containsKey(alpha)) { start = Math.max(map.get(alpha), start); } ans = Math.max(ans, end - start + 1); map.put(s.charAt(end), end + 1); } return ans; } }
|
转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 2113132982@qq.com