C++刷剑指offer(面试题48. 最长不含重复字符的子字符串)【双指针】

糖逗

题目描述：

1. 请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
   
2. 
   
3.  
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: "abcabcbb"
   
8. 输出: 3
   
9. 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
   
10. 示例 2:
    
11. 
    
12. 输入: "bbbbb"
    
13. 输出: 1
    
14. 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
    
15. 示例 3:
    
16. 
    
17. 输入: "pwwkew"
    
18. 输出: 3
    
19. 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
    
20.      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
    
21.  
    
22. 
    
23. 提示：
    
24. 
    
25. s.length <= 40000
    
26. 
    
27. 来源：力扣（LeetCode）
    
28. 链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof
    
29. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <map>
   
3. #include <string>
   
4. 
   
5. using namespace std;
   
6. 
   
7. int solution(string input){
   
8.         map<char, int> temp;
   
9.         int result = 0, right = 0, left = 0;
   
10.         while(right < input.size()){
    
11.                 if(temp.find(input[right]) != temp.end()){
    
12.                         left = max(left, temp[input[right]] + 1);
    
13.                 }
    
14.                 temp[input[right++]] = right;
    
15.                 result = max(right - left, result);
    
16.         }
    
17.         return result;
    
18. }
    
19. 
    
20. int main(void){
    
21.         string input;
    
22.         cin >> input;
    
23.         int res = solution(input);
    
24.         cout << res << endl;
    
25.         return 0;
    
26. }

复制代码

注意事项：
1.参考链接：https://leetcode-cn.com/problems ... g-zhi-zhen-shi-xia/
2.temp.find(input[right]) != temp.end()为在map中查找到元素更新left。

糖逗