首页 > 其他 > 详细

3. Longest Substring Without Repeating Characters

时间:2017-04-04 09:33:40      阅读:223      评论:0      收藏:0      [点我收藏+]

题目:

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 the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

链接:https://leetcode.com/problems/longest-substring-without-repeating-characters/#/description

4/3/2017

36%, 36ms

 1 public class Solution {
 2     public int lengthOfLongestSubstring(String s) {
 3         int maxCount = 0;
 4         Set<Character> set = new HashSet<Character>();
 5         int start = 0;
 6 
 7         for (int i = 0; i < s.length(); i++) {
 8             if (set.contains(s.charAt(i))) {
 9                 if (set.size() > maxCount) maxCount = set.size();
10                 while (s.charAt(start) != s.charAt(i)) {
11                     set.remove(s.charAt(start));
12                     start++;
13                 }
14                 start++;
15             }
16             set.add(s.charAt(i));
17         }
18         if (set.size() > maxCount) maxCount = set.size();
19         return maxCount;
20     }
21 }

官方答案里有更加优化的解法,不需要从set当中把之前的去掉:

 1 public class Solution {
 2     public int lengthOfLongestSubstring(String s) {
 3         int n = s.length(), ans = 0;
 4         Map<Character, Integer> map = new HashMap<>(); // current index of character
 5         // try to extend the range [i, j]
 6         for (int j = 0, i = 0; j < n; j++) {
 7             if (map.containsKey(s.charAt(j))) {
 8                 i = Math.max(map.get(s.charAt(j)), i);
 9             }
10             ans = Math.max(ans, j - i + 1);
11             map.put(s.charAt(j), j + 1);
12         }
13         return ans;
14     }
15 }

官方详细解答:https://leetcode.com/articles/longest-substring-without-repeating-characters/

更多讨论:https://discuss.leetcode.com/category/11/longest-substring-without-repeating-characters

3. Longest Substring Without Repeating Characters

原文:http://www.cnblogs.com/panini/p/6664260.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!