滑动窗口

Posted on | Post modified: | In |
Words count in article: 840

3. 最大无重复子串

  • 题目描述

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

示例 1:

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

示例 2:

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

示例 3:

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

  寻找无重复子串，很适合用滑动窗口的方法。需要维护的是窗口的大小（包括起始位置）。在维护窗口大小的过程中，需要在子串中查找是否有与新来的字符相同的字符，若直接采用线性扫描，复杂度较高。而字符只有256个ASCII码，因此可以建立一个关于字符的hash表，对每次滑动得到的新字符，可以在hash表中快速查看是否存在，还需注意查找是在子串范围内查找，所以即使hash表中有，还应判断是否在子串范围内。现在分情况讨论，什么情况应更新什么：

  • 1. 若无重复字符，子串长度会增长，此时新的最大子串长度应是增长后的长度与记录的最大子串的长度中最大的那个。

  • 2. 若有重复字符，无需更新最大长度，此时应更新滑动窗口的左边界。

  • 3. 注意，每次滑动都需要更新右边界，所以这是个固定操作，写在这两种情况外。

PS：还需注意的是边界的下标选择问题，因为数组与字符串地址从0开始，所以读取第一个字符是从0开始，那么左边界与当前所指位置（或者说右边界）重合的话也有一个字符，显然不合理。因此应选择一个边界挪动一个位置，为了直观，我选择左边界left指着真实窗口的前面一位。这时可将left与hash表都初始化为-1，代表当前位置没有内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
    int lengthOfLongestSubstring(string s) {
    int hash[256] ;
    for(int i=0;i<256;i++){
        hash[i] = -1;
    }
    int left=-1,subsize = 0;

    for(int i = 0; i<s.length(); i++){
        //当某字符还未出现过，或出现位置在左边界外(左)，更新最大子串长度
        if(hash[s[i]] == -1 || left > hash[s[i]] )
            subsize = max(subsize , i-left);
        else   //出现过，且在左边界内(右)，更新左边界
            left = hash[s[i]];  
        hash[s[i]] = i; //更新最近出现位置
    }
	return subsize;
	}
};

  上面策略是保存最近出现的位置，与左边界比较，也可保存子串内各个字符出现的次数，维护次数为1。

1
2
3
4
5
6
7
int count = 0;
    for(int i = 0, j = 0; i < n; i++){
        h[a[i]]++; //子串添加i位置的数字
        while( h[a[i]] > 1 )
            h[a[j++]]--; //左边界位置的数字去掉，并右移左边界，直到子串无重复
        count = max(count, i-j+1);
    }

子串