无重复字符的最长子串

题目描述

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

解法（滑动窗口）

使用"滑动窗口"解决问题：

1. left =0,right = 0
2. 进窗口
3. 判断 是否出窗口
4. 更新结果

起初left和right都为0，判断right的字符是否在哈希表中存在，不在的话将其置入，并且继续将right右移；如果该字符已经存在那么先记录一个结果 再将left右移。

 left需要右移至right当前字符相同的那个的后一个。

因为如果在right相同字符前依旧会有重复的字符。

此时，继续将right右移，重复以上步骤。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0, right = 0;
        // 用数组模拟hash,记录每个字符出现的次数
        int hash[128] = {0};
        int n = s.length();
        int ret = 0;

        while (right < n) {
            hash[s[right++]]++;          // 进入窗口
            while (hash[s[right-1]] > 1) { // 判断
                hash[s[left++]]--;       // 出窗口
            }
            ret = max(ret, right - left );
        }

        return ret;
    }
};