题目:给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
最优时间复杂度(O(n)) -- 滑动窗口:
class Solution { public int lengthOfLongestSubstring(String s) { // 哈希集合,记录每个字符是否出现过 Set<Character> occ = new HashSet<Character>(); int n = s.length(); // 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动 int rk = -1, ans = 0; for (int i = 0; i < n; ++i) { if (i != 0) { // 左指针向右移动一格,移除一个字符 occ.remove(s.charAt(i - 1)); } while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) { // 不断地移动右指针 occ.add(s.charAt(rk + 1)); ++rk; } // 第 i 到 rk 个字符是一个极长的无重复字符子串 ans = Math.max(ans, rk - i + 1); } return ans; } }
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; } }