LeetCode刷题--点滴记录003

水深无声 2023-09-28 09:22 132阅读 0赞

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

**要求**

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

**解题**

#### C++版本 ####

#include <iostream>
    using namespace std;
    #include <set>
    
    class Solution {
        
    public:
        int lengthOfLongestSubstring(string s)
        {
        
            if (s.size() == 0) 
                return 0;
            int max_len = 0;             //用来保存最长子串长度
            set<char> book;             //记录窗口中已经出现的字符
            int left = 0;               // 维护滑动窗口的起始位置
            for (int right = 0; right < s.length(); ++right)
            {
        
                // 当新加入窗口右侧的字符是重复字符，让窗口左边界（左指针）右移
                while (book.find(s[right]) != book.end()) {
        
                    book.erase(s[left]);
                    ++left;
                }
                
                book.insert(s[right]); // 将右指针处的字符加入窗口
                max_len = max(max_len, right - left + 1); //更新最大长度
            }
            return max_len;
        }
    };
    
    
    void test01()
    {
        
        Solution s;
        string s1 = "abcabcbb";
        cout << s1 << endl;
        int l1 = s.lengthOfLongestSubstring(s1);
        cout << l1 << endl;
    }
    
    void test02()
    {
        
        Solution s;
        string s2 = "bbbbb";
        cout << s2 << endl;
        int l2 = s.lengthOfLongestSubstring(s2);
        cout << l2 << endl;
    }
    
    void test03()
    {
        
        Solution s;
        string s3 = "pwwkew";
        cout << s3 << endl;
        int l3 = s.lengthOfLongestSubstring(s3);
        cout << l3 << endl;
    }
    
    int main()
    {
        
        test01();
        cout << "------------------" << endl;
        test02();
        cout << "------------------" << endl;
        test03();
    
        system("pause");
        return 0;
    }

![在这里插入图片描述][468dbe91825f4014aff2e059e74abad3.png_pic_center]

#### Python版本 ####

class Solution:
        def lengthOfLongestSubstring(self, s: str) -> int:
            if not s: 
                return 0
            max_len = 0             # 最大长度
            book = []                 # 放字符串的一个队列    
            for a in s:
                while a in book:
                    del book[0]       # 删除队列左边第一个，直到没有重复的字符串
                book.append(a)       
                max_len = max(max_len,len(book)) 
            return max_len
                           
               
    def test01():
        solution = Solution()
        s1 = "abcabcbb"
        print(s1)
        l1 = solution.lengthOfLongestSubstring(s1)
        print(l1)
        
    def test02():
        solution = Solution()
        s2 = "bbbbb"
        print(s2)
        l2 = solution.lengthOfLongestSubstring(s2)
        print(l2)
        
    def test03():
        solution = Solution()
        s3 = "pwwkew"
        print(s3)
        l3 = solution.lengthOfLongestSubstring(s3)
        print(l3)
                
    if __name__=="__main__":
        test01()
        print("--------------")
        test02()
        print("--------------")
        test03()

![在这里插入图片描述][19c62a0aaa8943c5811e15dc68cdc95b.png_pic_center]

#### Java版本 ####

package com.hailei_01;
    
    import java.util.HashMap;
    import java.util.Map;
    
    public class LongestSubstringWithoutRepeatingCharacters {
        
        public static void main(String[] args) {
        
            String s1 = "abcabcbb";
            System.out.println(s1);
            int l1 = lengthOfLongestSubstring(s1);
            System.out.println(l1);
            System.out.println("----------------");
            String s2 = "bbbbb";
            System.out.println(s2);
            int l2 = lengthOfLongestSubstring(s2);
            System.out.println(l2);
            System.out.println("----------------");
            String s3 = "pwwkew";
            System.out.println(s3);
            int l3 = lengthOfLongestSubstring(s3);
            System.out.println(l3);
        }
    
        public static int lengthOfLongestSubstring(String s) {
        
            int max_len = 0;//用于记录最大不重复子串的长度
            Map<Character, Integer> map = new HashMap<Character, Integer>();
            for (int right = 0, left = 0; right < s.length(); right++) {
        
                if (map.containsKey(s.charAt(right))) {
        
                    left = Math.max(map.get(s.charAt(right)), left);
                }
                max_len  = Math.max(max_len , right - left + 1);
                map.put(s.charAt(right), right + 1);//下标 + 1 代表 i 要移动的下个位置
            }
            return max_len;
        }
    
    }

![在这里插入图片描述][00a7cd0078c14f938bb3d5c30b980bd7.png_pic_center]

**希望本文对大家有帮助，上文若有不妥之处，欢迎指正**

**分享决定高度，学习拉开差距**

[468dbe91825f4014aff2e059e74abad3.png_pic_center]: https://img-blog.csdnimg.cn/468dbe91825f4014aff2e059e74abad3.png#pic_center
[19c62a0aaa8943c5811e15dc68cdc95b.png_pic_center]: https://img-blog.csdnimg.cn/19c62a0aaa8943c5811e15dc68cdc95b.png#pic_center
[00a7cd0078c14f938bb3d5c30b980bd7.png_pic_center]: https://img-blog.csdnimg.cn/00a7cd0078c14f938bb3d5c30b980bd7.png#pic_center