LeetCode——Longest Substring Without Repeating Characters

本文主要是介绍LeetCode——Longest Substring Without Repeating Characters，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given a string, find the length of the longest substring without repeating characters.

• Example 1:
  Input: “abcabcbb”
  Output: 3
  Explanation: The answer is “abc”, with the length of 3.
• Example 2:
  Input: “bbbbb”
  Output: 1
  Explanation: The answer is “b”, with the length of 1.
• Example 3:
  Input: “pwwkew”
  Output: 3
  Explanation: 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.

解法一

用HashMap来保存字符与字符出现的位置，用left和i来管理一个滑动窗口，如果当前遍历到的值在窗口内出现过，则更新left指向这个值出现过的位置，然后比较max与i-left的大小决定是否要更新max，再更新当前这个字符的新位置；如果未出现过这个字符则将其加入map。

public int lengthOfLongestSubstring(String s) {if(s==null||s.length()==0)return 0;int left=-1;int max=0;HashMap<Character,Integer> map=new HashMap<Character, Integer>();for(int i=0;i<s.length();i++){if(map.containsKey(s.charAt(i))&&map.get(s.charAt(i))>left){left=map.get(s.charAt(i));map.replace(s.charAt(i), i);}else{map.put(s.charAt(i), i);}max=max>i-left?max:i-left;	}return max;}

Runtime: 23 ms, faster than 88.72% of Java online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 39.8 MB, less than 15.92% of Java online submissions for Longest Substring Without Repeating Characters.\

解法二

核心思想与方法一类似，但是用一个长度为256的数组来代替HashMap，是的代码更加简洁

public int lengthOfLongestSubstring(String s) {int[] m=new int[256];Arrays.fill(m, -1);int max=0,left=-1;for(int i=0;i<s.length();i++){left=Math.max(left, m[s.charAt(i)]);m[s.charAt(i)]=i;max=Math.max(max, i-left);}return max;}

Runtime: 15 ms, faster than 100.00% of Java online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 40.1 MB, less than 13.33% of Java online submissions for Longest Substring Without Repeating Characters.
参考

解法三

用HashSet保存字符，如果当前字符存在于set中了，那么就删除重复的字符和重复字符之前的所有字符

public int lengthOfLongestSubstring(String s) {int max=0,left=0;HashSet<Character> t=new HashSet<Character>();for(int i=0;i<s.length();i++){if(!t.contains(s.charAt(i))){t.add(s.charAt(i));max=Math.max(max, t.size());}else{while(t.contains(s.charAt(i)))t.remove(s.charAt(left++));t.add(s.charAt(i));}}return max;}

Runtime: 24 ms, faster than 85.59% of Java online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 39.9 MB, less than 15.36% of Java online submissions for Longest Substring Without Repeating Characters.

这篇关于LeetCode——Longest Substring Without Repeating Characters的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---