3. 自我刷题之无重复字符的最长子串

回归次数：1

题目：

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例：

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解答：

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {

    /**
     * 最基础遍历,时间复杂度：O(n ^3) 性能很差
     * @param s
     * @return
     */
   public int lengthOfLongestSubstring(String s) {

       int n = s.length();
       int ans = 0;
       for(int i = 0;i < n;i ++){

           for(int j = i + 1;j <= n;j ++){
               if (allUnique(s,i,j)){
                   ans = Math.max(ans,j - i);
               }
           }
       }

       return ans;
    }


    public boolean allUnique(String s,int start,int end){

        Set<Character> set = new HashSet<>();
        for(int i = start;i < end;i ++){

            Character ch = s.charAt(i);
            if (set.contains(ch))return false;
            set.add(ch);
        }
        return true;
    }

    /**
     * 滑动窗口   会把最大的不重复字符串留住，最后留在窗口里面的不一定是最大的不重复字符串
     * 空间复杂度：O(2n) = O(n)
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring2(String s) {

        int n = s.length();
        int ans = 0 , i = 0, j = 0;
        Set set = new HashSet();
        while (i < n && j< n){

            if (!set.contains(s.charAt(j))){

                set.add(s.charAt(j));
                j += 1;
                ans = Math.max(ans,j - i);
            }else{
                set.remove(s.charAt(i));
                i += 1;
            }
        }

        return ans;
    }

    /**
     * 滑动窗口优化，Set改为Map存储，减少了查找对比的时间复杂度
     * @param s
     * @return
     */
    public int lengthOfLongestSubstring3(String s) {

        int n = s.length();
        int ans = 0 , i = 0, j = 0;
        /**
         * 使用map减少了比对的时候的查找时间复杂度，不需要遍历整个set，O(n),map直接O(1)查找对比
         */
        Map<Character,Integer> map = new HashMap();
        while (i < n && j< n){

            if (!map.containsKey(s.charAt(j))){

                map.put(s.charAt(j),j);
                j += 1;
                ans = Math.max(ans,j - i);
            }else{
                map.remove(s.charAt(i));
                i += 1;
            }
        }

        return ans;
    }

    public static void main(String[] args) {

       Solution s = new Solution();
        System.out.println(s.lengthOfLongestSubstring3("pwwkew"));
    }
}