利用滑动窗口法解决无重复字符的最长子串

￡神魔★判官ぃ 2022-12-23 09:38 101阅读 0赞

**[无重复字符的最长子串][Link 1]**

*  **题目描述：**

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

**示例** **1:**

**输入****:** "abcabcbb"

**输出****:** 3

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

**示例** **2:**

**输入****:** "bbbbb"

**输出****:** 1

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

**示例** **3:**

**输入****:** "pwwkew"

**输出****:** 3

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

请注意，你的答案必须是 **子串**的长度，"pwke" 是一个*子序列，*不是子串。

*  **解题思路：**

采用滑动窗口法搜索最长子串

只需要考虑左边界和右边界的确立问题，以及如何移动到的问题

对此

**设立左指针****a****和右指针****b**

**b****指针向右侧伸缩****\{**

**对每个****A\[b\]****判断是否在之前的数组出现过****;**

**如果出现，指针****a****指向出现过的位置的下一个位置****;****更新右指针和最大长度****;**

**\}**

*  **具体算法流程如图所示**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5][]

*  **具体代码如下**

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            //滑动窗口
            int start=0,end=0;
            int len=0,res=0;
            while(end<s.size())
            {
                char tmp=s[end];//先将end暂存  方便与滑窗里比较
                for(int i=start;i<end;i++)
                {
                    if(tmp==s[i])//存在相同的
                    {
                        start=i+1;//左边界,跳过相同数字，移动至相同数字的下一位置处
                        len=end-start;
                        break;
                    }
                }
                end++;//右边界搜索
                len++;
                res=max(res,len);//找到长度最长的子串
            }
            return res;
        }
    };

参考来源：leetcode算法

[Link 1]: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221120/ab6d3bc9bd1b4d5890977c41f7d49fee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221120/4bd64ddd18194793bc184dde28a6403c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2]: /images/20221120/276b76239d5e43daa2197696c460256c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3]: /images/20221120/55412be43ee14bd08275189926c198f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4]: /images/20221120/00c4ee9ff20e42e9a35cd97c2dc88eea.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5]: /images/20221120/eeed0b70eecf401b8d5fba9c08d77ad1.png