本文共 4012 字,大约阅读时间需要 13 分钟。
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.
class Solution { public int lengthOfLongestSubstring(String s) { if(s == null || s.length() == 0) return 0; if(s.length() == 1) return 1; int left = 0, right = 0, max = 0; boolean[] used = new boolean[128]; while(right < s.length()){ if(used[s.charAt(right)] == true){ used[s.charAt(left)] = false; while(left < right){ used[s.charAt(right)] = false; right--; } right++; left++; } if(used[s.charAt(right)] == false){ used[s.charAt(right)] = true; right++; } max = Math.max(max,(right - left)); } return max; }}
2019.11.10 update:
首先想到的就是sliding windowclass Solution { public int lengthOfLongestSubstring(String s) { if(s == null || s.length() == 0) { return 0; } int left = 0; int right = 0; int max = 0; HashSetset = new HashSet<>(); while(right < s.length()) { if(!set.contains(s.charAt(right))) { set.add(s.charAt(right)); right++; if(right - left > max) { max = right - left; } } else { set.remove(s.charAt(left)); //注意在这里只移左边! left++; } } return max; }}
leetcode solution 1
时间复杂度:O(n),最坏情况O(2n) 空间复杂度:O(min(size of charset, n))public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); Setset = new HashSet<>(); int ans = 0, i = 0, j = 0; while (i < n && j < n) { // try to extend the range [i, j] if (!set.contains(s.charAt(j))){ set.add(s.charAt(j++)); ans = Math.max(ans, j - i); } else { set.remove(s.charAt(i++)); } } return ans; }}
数组版sliding window解法
class Solution { public int lengthOfLongestSubstring(String s) { if(s == null || s.length() == 0) return 0; if(s.length() == 1) return 1; int left = 0, right = 0, max = 0; boolean[] used = new boolean[128]; while(right < s.length()){ if(used[s.charAt(right)] == true){ used[s.charAt(left)] = false; left++; } else{ used[s.charAt(right)] = true; right++; max = Math.max(max,(right - left)); } } return max; }}
leetcode solution 2
Instead of using a set to tell if a character exists or not, we could define a mapping of the characters to its index. Then we can skip the characters (直接把 i 跳到重复的地方)immediately when we found a repeated character.public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; Mapmap = new HashMap<>(); // current index of character // try to extend the range [i, j] for (int j = 0, i = 0; j < n; j++) { if (map.containsKey(s.charAt(j))) { i = Math.max(map.get(s.charAt(j)), i); } ans = Math.max(ans, j - i + 1); map.put(s.charAt(j), j + 1); } return ans; }}
int[26] for Letters ‘a’ - ‘z’ or ‘A’ - ‘Z’
int[128] for ASCII int[256] for Extended ASCII
2019.3.27创建:完成
转载地址:http://wfqvb.baihongyu.com/