滑动窗口法

题目：给定一个字符串，找出其中不含重复字符的最长子串的长度

---

题目分析：题意为字符串中不含重复字符的子串，也就是子串必须是给定字符串中连续的。

例如：给定字符串“abacad”那么最长子串为“bac”或"cad"而不是“abcd”。

滑动窗口法可以解决字符串/数组 子串的问题，可以将嵌套的循环问题转换为单循环问题，降低时间复杂度。

image

使用窗格圈出字符串中无重复字符的每个子串，比较子串长度。

上代码：

public int longestSubstring(String s){
  //定义字符串长度，返回结果，窗口左边界，窗口右边界
  int n = s.length(), res = 0, left = 0, right = 0;
  //定义存放元素位置的map
  Map<Character, Integer> map = new HashMap<Character, Integer>();
  while(left < n && right < n){
    if(map.containsKey(s.charAt(j))){
                i=Math.max(i, map.get(s.charAt(j))+1);//如果包含key的话，将移动窗口的左边界调整为重复数字的下一个位置;
            }
            map.put(s.charAt(j), j);//更新重复出现元素的value值
            ans = Math.max(ans, j-i+1);
            j++;
  }
}