3. 无重复字符的最长子串

image.png

// /*
// 暴力法：简单易懂，但是时间复杂度太高O（n^3）,会超时间。需要注意点是边界。规定好[i,j).
// */

// public class Solution{
//  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+1;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;
//  }

// }



/*
滑动窗口：
在暴力法中，如果，sij为不重复子序列 j每次加一 时 会的重复遍历i到j-1的每一个
这样复杂度会降到O（n^2）.
通过使用 HashSet 作为滑动窗口，我们可以用O（1） 完成对字符是否
在当前的子字符串中。
*/


// public class Solution{
//  public int lengthOfLongestSubstring(String s){
//      int n = s.length();
//      Set<Character> set = new HashSet<>();
//      int ans = 0,i = 0,j = 0;

//      while(i<n && j<n){
//          if(!set.contains(s.charAt(j))){
//              set.add(s.charAt(j));
//              j++;
//              ans = Math.max(ans,j-i);
//          }else{
//              set.remove(s.charAt(i));
//              i++;
//          }


//      }
//      return ans;

//  }


// }




/*
优化的滑动窗口:
利用HashMap的key的唯一性，来判断是否，已经重复。
将value 存放下一次的，开始的地址，j+1


*/

public class Solution{
    public int lengthOfLongestSubstring(String s){
        int n = s.length(), ans = 0;
        Map<Character,Integer> map = new HashMap<>();

        for(int i = 0,j = 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;

    }
}

leetcode