[算法] 滑动窗口算法--查找最长子串

╰+哭是因爲堅強的太久メ 2023-01-17 03:17 145阅读 0赞

# 滑动窗口 #

滑动窗口也叫尺取法，是一种在字符串或数组中查找满足条件的算法。  
  例如可以在字符串中查找满足条件的子串。

## 滑动窗口图示 ##

在这里，规定窗口大小为3，每次向右滑动一位。  
  当然，窗口的大小可以随意调整，调整至满足条件即可。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]

# 2. 利用滑动窗口查找最长子串 #

## 基本原理 ##

### 思路一： ###

规定开始窗口大小为0，利用左右指针指向子串的开始和结束。截取左右指针中的子串，每次移动右边指针将元素加入子串并判断在子串中是否有相同元素，如果有则移动左指针。一直重复上述操作，直到右指针指向字符串尾。记录出现的最长子串。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 1]  
代码：

// 判断右指针元素是否在前方出现，没有出现则扩大窗口大小，元素出现则改变左指针位置
    // 此方法利用滑动窗口将窗口的字符串截取出来存到子串中，判断子串中是否包含即将加入的字符串，
    int lengthOfLongestSubstring(string s) { 
        if (s.length() <= 1)
        { 
            return s.length();
        }
    
        int left = 0, right = 0;
        int maxlen = 0;
    
        while (right <= s.length())
        { 
            // 截取子串
            string sub = s.substr(left, right - left);
            maxlen = maxlen > right - left ? maxlen : right - left;
            
            // 判断子串中是否含有新加入的字符，如果含有新加入的字符，改变窗口大小
            while ( left < right && sub.find(s[right]) != string::npos)
            { 
                left++;
                // 窗口大小发生改变 截取新串
                sub = s.substr(left, right - left);
            }
    
            right++;
        }
    
        return maxlen;
    }

### 思路二： ###

原理与上述相同，但不用截取子串，效率更高。

int lengthOfLongestSubstring(string s) { 
    	if (s.length() <= 1)
    	{ 
    	    return s.length();
    	}
    
        int left = 0, right = 1, max = 1;
    
        while (right < len)
        { 
            // 在子串中进行查找该字符第一次出现的位置，如果第一次出现的位置与右值相同，则代表没有出现过该字符
            while (right < len && s.find(s[right], left) == right)
            { 
                right++;
            }
            max = right - left > max ? right - left : max;
            left++;
        }
        return max;
    }

# 思路三： #

与上述思路完全不同，不再利用滑动窗口。出现一个字符记录一个字符，并且累加器累加，如果遇到已经出现过的字符，则根据这个重复字符出现在字符串中的位置，决定累加器的值。重复上述操作，记录最大累加器的值。

int lengthOfLongestSubstring(string s) { 
        if (s.length() <= 1)
        { 
            return s.length();
        }
    
        int acsii[256] = {  0 };     // 记录字符串出现的次数
        int count = 0;
        int maxcount = 1;
    
        for (int i = 0; i < s.length(); i++)
        { 
            // 如果字符已经出现
            if (acsii[s[i]] == 1)
            { 
                // 判断前后时候是一样的字符串，如果重复，则当前字符为新子串，则让计数器重新计数
                if (s[i] == s[i - 1])
                { 
                    //如果计数器大于字符串一半长度则说明不会出现更长子串, 所以清零也就没有必要了
                    if (count > s.length() / 2)
                    { 
                        break;
                    }
                    count = 0;
                }  
                else
                { 
                    // 如果该串与周边字符串没有关系，则对长度-1，再开始计数，
                    count--;  
                }  
            }
           
            // 如果没有字符出现则累加器++，如果有字符出现过则对长度改变后再++
            count++;
            acsii[s[i]] = 1;
            maxcount = maxcount > count ? maxcount : count;
        }
    
        return maxcount;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/7d6132399afe4ab99bd410a3a86c4496.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzcxNzUyMA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/63721b786cfa456ca2ff925b3149b02a.png