本文共 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 window

class Solution {
       public int lengthOfLongestSubstring(String s) {
           if(s == null || s.length() == 0) {
               return 0;        }        int left = 0;        int right = 0;        int max = 0;        HashSet
   
     set = 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();        Set
   
     set = 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;        Map
   
     map = 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;    }}
   

总结

1. 在不知道string大小的情况下用map比较保险，如果已知string比较小，可以直接使用数组

int[26] for Letters ‘a’ - ‘z’ or ‘A’ - ‘Z’

int[128] for ASCII

int[256] for Extended ASCII

2. solution 1的sliding window感觉很聪明。如果遇到了重复的右指针可以一直不动而只移动左指针，直到左指针指向重复元素并删除，再重新开始新一轮的搜索。
3. solution 2用 j-i 的值来表示长度。当 j 遇到重复的元素时，i 直接跳到重复的元素那。省去了存储每一个元素的访问情况，而通过索引的相对位置来记录。厉害！

2019.3.27创建：完成

转载地址：http://wfqvb.baihongyu.com/