思路一 ：滑动窗口（双指针）

题目中要求答案必须是子串的长度，意味着子串内的字符在原字符串中一定是连续的。因此我们可以将答案看作原字符串的一个滑动窗口，并维护窗口内不能有重复字符，同时更新窗口的最大值。

算法

• 初始化头尾指针 head，tail；
• tail 指针右移，判断 tail 指向的元素是否在 [head:tail] 的窗口内；
• 如果窗口中没有该元素，则将该元素加入窗口，同时更新窗口长度最大值res，tail 指针继续右移；
• 如果窗口中存在该元素，则将 head 指针右移，直到窗口中不包含该元素。
• 此处可以利用哈希表优化head指针，即用哈希表存储各个字符对应的原来的存储位置temp，根据temp是否比head大，则可知当前tail指向元素是否在滑动窗口之中，若在，则将head更新为temp,若不在，则直接取head,即max(head,temp),同时要记得更新索引temp
• 返回窗口长度的最大值res。

代码

• cpp

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int i = -1,res = 0;
        unordered_map<char,int> map;
        for(int j = 0;j < s.size();j++){
            if(map.count(s[j]) != 0){
                i = max(i,map[s[j]]);
            }
            map[s[j]] = j;
            res = max(res,j-i);
        }
        return res;
    }
};

• java

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int i = -1,res = 0;
        Map<Character,Integer> map = new HashMap<>();
        for(int j = 0;j < s.length();j++){
            if(map.containsKey(s.charAt(j))){
                i = Math.max(i,map.get(s.charAt(j)));
            }
            map.put(s.charAt(j),j);
            res = Math.max(res,j-i);
        }
        return res;
    }
}

##思路二 : 动态规划

• 思路如下

总结

滑动窗口非常适用于子串类的各种问题，需要好好的反复掌握，理解其中的原理,对此题，也可以使用双指针，动态规划来进行解题，事实上，双指针和滑动窗口在本题实质上是一样的，动态规划需要根据迭代关系，即判断字符所在原来的索引是否比当前左边界i大，若大，则需要更新dp[j] = j-i,否则dp[j] = dp[j-1]+1