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

1. 题目描述：

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

示例 1:

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是子串的长度，"pwke" 是一个子序列，不是子串。

2. 解题思路

2.1 滑动窗口

　定义一个左指针，一个右指针，左指针遍历所有元素。每移动一次右指针，在hash集合中查找当前元素是否已在集合里（以元素为查找）。若在，结束当前循环，右移一位左指针指针，集合移除当前元素；若不在，添加进hash集合。

2.1.1 C++

(a) set

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4         // 哈希集合，记录每个字符是否出现过
 5         unordered_set<char> occ;
 6         int n = s.size();
 7         // 右指针，初始化为-1，相当于我们在字符串左边界的左侧，还没有开始移动
 8         int rk = -1, ans = 0;
 9         // 枚举左指针的位置，初始值隐性地表示为-1
10         for(int i = 0; i < n; i++){
11             if(i != 0){
12                 // 左指针向右移动一格，移除一个字符
13                 occ.erase(s[i-1]);
14             }
15             // 在哈希集合里查找当前元素是否已存在，存在则重复
16             while(rk + 1 < n && !occ.count(s[rk + 1])) {
17                 //不断移动右指针
18                 occ.insert(s[rk + 1]);
19                 rk++;
20             }
21             // 第 i 到 rk 个字符是一个极长的无重复字符子串
22             ans = max(ans, rk - i + 1);
23         }
24         return ans;
25     }
26 };

(b) vector

 1 class Solution {
 2 public:
 3     int lengthOfLongestSubstring(string s) {
 4 
 5             // 第二种
 6             vector<int> m(128, 0); // ASCII码范围：0-127
 7             // i: 左指针的位置，ans：最长子串，n：字符串长度
 8             int i = 0, ans = 0, n = s.size();
 9             // 遍历所有左指针
10             for(int j = 0; j < n; j++){
11                 // 查看当前元素是否重复，若m[s[j]] < i:表示当前元素在左指针左边出现过，i不变；若
12                 // m[s[j]] > i:表示当前元素在 i 的右边，则左指针i等于当前元素的位置的右边一个
13                 // 元素位置。
14                 if(m[s[j]] != 0){
15                     i = max(i, m[s[j]]);
16                 }
17                 // 存储当前元素为其右边位置
18                 m[s[j]] = j + 1;
19                 ans = max(ans, j - i + 1);
20             }
21             return ans;
22         }
23 };

2.1.2 Java

 1 class Solution {
 2     public int lengthOfLongestSubstring(String s) {
 3        // 哈希集合，记录每个字符是否出现过
 4        Set<Character> occ = new HashSet<Character>();
 5        // 字符数组的长度
 6        int n = s.length(); 
 7        int rk = -1, ans = 0;
 8        for(int i = 0; i < n; i++){
 9            if(i != 0){
10                //左指针向右移动一格，移除一个字符
11                occ.remove(s.charAt(i - 1));
12            }
13            // 在集合里查找当前元素是否已存在
14            while(rk + 1 < n && !occ.contains(s.charAt(rk + 1))){
15                // 不断移动右指针
16                occ.add(s.charAt(rk + 1));
17                rk++;
18            }
19            ans = Math.max(ans, rk - i + 1);
20        }
21        return ans;
22     }
23 }

2.1.3 Python

 1 class Solution:
 2     def lengthOfLongestSubstring(self, s: str) -> int:
 3         # 哈希集合，记录每个字符是否出现过
 4         occ = set()
 5         n = len(s)
 6         # 右指针，初始值为0，相当于我们在字符串的左边界的左侧，还没开始移动
 7         rk, ans = 0, 0
 8         for i in range(n):
 9             if i != 0:
10                 occ.remove(s[i-1])
11             while rk < n and s[rk] not in occ:
12                 # 不断移动右指针
13                 occ.add(s[rk])
14                 rk += 1
15             ans = max(ans, rk - i)
16         return ans

3. 结语

　　努力去爱周围的每一个人，付出，不一定有收获，但是不付出就一定没有收获！给街头卖艺的人零钱，不和深夜还在摆摊的小贩讨价还价。愿我的博客对你有所帮助(*^▽^*)(*^▽^*)！

　如果客官喜欢小生的园子，记得关注小生哟，小生会持续更新(#^.^#)(#^.^#)。