题目

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

题目链接

暴力解法

遍历字符串，找每个字符为首的最长子串。时间复杂度为O(n)*O(以首字符开始的字符串)，寻找首字符开始的字符串时间复杂度O(n^2)，总的时间复杂度为O(n^3)。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0; //要考虑到空串的情况
        int length=0;
        for(int i=0; i<s.length(); i++){
            length = 1;
            for(int j=i+1; j<s.length(); j++){
                String str = s.substring(i,j);// 子串范围s[i,j)
                if(str.indexOf(s.charAt(j)) < 0){//indexOf也是O(n)的方法，所以总的时间复杂度时O(n^3)
                    length ++;
                } else{
                    break;
                }
            }
            if(length>maxLength){
                maxLength = length;
            }
        }
        return maxLength;
    }
}

哈希解法

用哈希表，可以减少找每个字符为首的最长子串的时间，那么就可以从最初的O(n^2)降低到O(n),总的时间复杂度就为O(n)*O(n)=0(n^2)

class Solution {
  public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        int length;// 要考虑到空串的情况
        for(int i=0; i<s.length(); i++){
            length = 0;
            HashMap<Character,Integer> map = new HashMap<Character,Integer>();
            for(int j=i; j<s.length(); j++){
                if(map.containsKey(s.charAt(j))==false){
                    length++;
                    map.put(s.charAt(j),1);
                }else{
                    break;
                }
            }
            if(maxLength<length){
                maxLength = length;
            }
            map.clear();
        }
        return maxLength;
    }
}

滑动窗口

万万没想到，本题的最佳时间复杂度竟然是O(n)，算法原理如下：
我们先用一个例子考虑如何在较优的时间复杂度内通过本题。
我们不妨以示例一中的字符串abcabcbb 为例，找出从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：

以(a)bcabcbb开始的最长字符串为(abc)abcbb
以a(b)cabcbb开始的最长字符串为a(bca)bcbb
以ab(c)abcbb开始的最长字符串为ab(cab)cbb
以abc(a)bcbb开始的最长字符串为abc(abc)bb
以abca(b)cbb开始的最长字符串为abca(bc)bb
以abcab(c)bb开始的最长字符串为abcab(cb)b
以abcabc(b)b开始的最长字符串为abcabc(b)b
以abcabcb(b)开始的最长字符串为abcabcb(b)

发现了子串的结束位置是非递减的，这里的原因在于，假设第k个字符作为起始位置，rk为终止位置。那么当我们选择第k+1个字符作为起始位置时，首先k+1到rk的位置显然是不重复的，并且我们还可以尝试继续增大rk(不必回到k+1的位置判断)。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        int rk = 0, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk < n && !occ.contains(s.charAt(rk ))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk));
                ++rk;
            }
            // 第 i 到 rk-1 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i );
        }
        return ans;
    }
}

知识点

String方法

String s = "1234abc";
// substring 左闭右开
s.substring(0,3); // 123 

// indexOf 可以求字符位置，也可以求字串位置
s.indexOf('a'); // 4
s.indexOf("23") // 1

// charAt(i) 求指定位置的字符    
s.charAt(0); // 1

哈希集合

// 初始化
Set<Character> occ = new HashSet<Character>();
// 移除元素
occ.remove('a'); 
// 添加元素
occ.add('a');