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

题目

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

示例 1:

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

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

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

解题

方法一：滑动窗口（逐个）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //char[] chars = new char[256];
        int chars[256]={0}; //ASCII表有127个字符 还有个128的副表 因此申请256个空间 用于计数
        int begin = 0;
        int res = 0;
        for(int i = 0;i<s.length();i++){
            while(begin <= i && chars[s.at(i)] > 0){//处理当前添加的字符重复的问题
                //下面代码是用于逐个往前滑动  去重
                chars[s.at(begin)]--;
                begin++;
            }
            chars[s.at(i)]++;//每次不重复子串的长度+1
            res = max(res,i - begin + 1);//记录不重复子串的最长长度
        }
        return res;
    }
};

注意
取单个字符操作：

• C++为 string.at()
• JAVA为 string.charAt()

• string也可以视为数组形式 直接取就可以 例如 s="abcd",s[2] = "c"。

  
  字符集

---

方法二

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> data;
        int begin = 0, result = 0;
        //i代表字串的起始位置，j表示字串的结束位置
        for (int j = 0; j < s.size(); j++) {
            if (data.find(s[j]) != data.end()) {
                begin = max(begin, data[s[j]]);//当有字符重复时更新字串起始位置
            }
            result = max(result, j - begin + 1);//判断当前字串与历史字串长度的大小
            data[s[j]] = j + 1;//记录并更新这个字符最近出现的位置 此处相当于存储之前与之重复的元素的下一个位置  
        }
        return result;
    }
};

        for (int j = 0; j < s.size(); j++) {
            if (data.find(s[j]) != data.end()) {
                begin = max(begin, data[s[j]]);//当有字符重复时更新字串起始位置
            }
            result = max(result, j - begin + 1);//判断当前字串与历史字串长度的大小
            data[s[j]] = j + 1;//记录并更新这个字符最近出现的位置  
        }

不能写为以下这种形式

        for (int j = 0; j < s.size(); j++) {
            if (data.find(s[j]) != data.end()) {
                begin = max(begin, data[s[j]]);//当有字符重复时更新字串起始位置
                begin++;
            }
            result = max(result, j - begin + 1);//判断当前字串与历史字串长度的大小
            data[s[j]] = j ;//记录并更新这个字符最近出现的位置
        }

错误

这种形式的错误在于，循环有时候会误加，我们本意是取重复元素的下一个作为开始，但是map存储了所有的元素，因此有时即使无效的重复也会进入循环，使begin+1，减少了长度。
上面例子就是，begin在第二个m处时，当运行到最后一个t，由于之前map有保存key为t，因此会进入循环，使begin++，因此长度变短，因此此时的操作属于误操作。
所以直接用数据存储下一个位置这种形式比较可靠。