【力扣Hot100】滑动窗口

维护一个区间i, j，一般的模板是：

for(int i = 0, j = 0; i < n; i ++) {
while(j < n && ...) ...
...
}

1. 无重复字符的最长子串

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

示例 1:

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

示例 2:

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

示例 3:

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

提示：

• 0 <= s.length <= 5 * 104
• s 由英文字母、数字、符号和空格组成

题解

两个指针 i, j，均从前往后遍历，维护 i, j 之间的字符是不重复的。

i表示左端点，j表示右端点。

当 j 进入窗口时，判断区间 i, j 之间，是否有 s[j] 存在，如果有，那么 i 应该 ++，直到区间 i , j 之间没有s[j]存在。这样就能确保i, j 之间的字符是不重复的。

可以用一个简单的数组来存，也可以用unordered_set，但是大家都用unordered_set所以我也用TAT

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> set;
        int n = s.size();
        int ans = 0;
        for(int i = 0, j = 0; j < n; j ++ ) {
            while(i < j && set.count(s[j])) {
                set.erase(s[i]);
                i ++;
            }
            set.insert(s[j]);
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
};

2. 找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s ****中所有 p ****的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入:s = "cbaebabacd", p = "abc"
输出:[0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

输入:s = "abab", p = "ab"
输出:[0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

提示:

• 1 <= s.length, p.length <= 3 * 104
• s 和 p 仅包含小写字母

题解

维护i, j 中间的区间是要比较的单词，i, j 区间大小是固定的，因此可以用一个变量来表示。

用长度为26的vector来存储字符串中的字母个数，如果它们是异位词，那么vector应该是相等的。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n = s.size(), m = p.size();
        if(n < m) return vector<int>();
        vector<int> ans;
        vector<int> pcnt(26), scnt(26);
        for(int i = 0; i < m; i ++ ) {
            pcnt[p[i] - 'a'] ++;
            scnt[s[i] - 'a'] ++;
        }
        if(pcnt == scnt) ans.push_back(0);
        for(int i = 0; i < n - m; i ++ ) {  // i表示即将踢出去的字符位置
            scnt[s[i] - 'a'] --;
            scnt[s[i + m] - 'a'] ++;
            if(scnt == pcnt) ans.push_back(i + 1);
        }
        return ans;
    }
};

原文地址：https://blog.csdn.net/Sophia2021XJTU/article/details/145159882

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！