LCR014-LCR017双指针

剑指offer（专项突破版）3.2 双指针

LCR014.字符串的排列

分析

• 变位词：组成各个单词的字母及每个字母出现的次数完全相同，只是字母排列的顺序不同。例如，”pots”、”stop”和”tops”就是一组变位词。
• 蛮力法：把字符串s1的字母所有排列组合找到，然后看s2中有没有这些子串。所有排列组合是n!，时间复杂度为O(n!)。
• 双指针法：用哈希表存储s1字符串字母的次数。然后用双指针，左指针i初始化指向s2开始，右指针j指向n-i+1，即字符串s1的长度。然后不断向右移动左指针和右指针，出现的字母要在哈希表中-1。

双指针解法代码

class Solution {
public:

    // 判断alphabet是否全0
    bool checkAllZero(vector<int> alphabet){
        for(int i = 0;i < 26;i++){
            if(alphabet[i] != 0){
                return false;
            }
        }
        return true;
    }

    bool checkInclusion(string s1, string s2) {
        // 边界检查
        if(s1.length() > s2.length()){
            return false;
        }
        // 哈希表存储26个字母
        vector<int> alphabet(26,0);
        // 对于s1中存在的字母，哈希表中的值+1
        int n = s1.length();
        for(int i = 0;i < n;i++){
            alphabet[s1[i]-'a']++;
        }
        // 对于s2中的子字符串，使用双指针
        int i = 0;
        int j = n-1;
        for(int k = i;k <= j;k++){
            alphabet[s2[k]-'a']--;

        }
        if(checkAllZero(alphabet)){
            return true;
        }
        j++;
        // 左右指针不断移动
        for(;j < s2.length();j++){
            alphabet[s2[i]-'a']++;
            alphabet[s2[j]-'a']--;
            if(checkAllZero(alphabet)){
                return true;
            }
            i++;
        }
        return false;
    }
};

复杂度分析

基于双指针和哈希表的算法需要扫描字符串s1和s2各一次。如果它们的长度分别是m和n，那么该算法的时间复杂度是O（m+n）。这种解法用到了一个数组。数组的长度是英文小写字母的个数（即26），是一个常数，也就是说，数组的大小不会随着输入字符串长度的变化而变化，因此空间复杂度是O（1）。

剑指offer（专项突破版）3.2 双指针

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

分析

LCR013题目的变形，一种直接的想法是在上一题的基础上，每次判断alphabet是否全0后不返回true or false，而是记录此时的下标i。

class Solution {
public:
    // 检查数组是否全0
    bool checkAllZero(vector<int> alphabet){
        for(int i = 0;i < 26;i++){
            if(alphabet[i] != 0){
                return false;
            }
        }
        return true;
    }

    vector<int> findAnagrams(string s, string p) {
        // 结果vector
        vector<int> res;
        // 处理边界条件
        int m = s.length();
        int n = p.length();
        if(m < n){
            return res;
        }
        // 定义哈希表
        vector<int> alphabet(26,0);
        // 记录p字符串的情况并更新s字符串的情况
        for(int j = 0; j < n; j++){
            alphabet[p[j]-'a']++;
            alphabet[s[j]-'a']--;
        }
        if(checkAllZero(alphabet)){
            res.push_back(0);
        }
        // 双指针遍历字符串s
        for(int i = 0, j = n; j < m; i++, j++){
            alphabet[s[i]-'a']++;
            alphabet[s[j]-'a']--;
            if(checkAllZero(alphabet)){
                res.push_back(i + 1);
            }
        }
        return res;
    }
};

复杂度分析

同样，这种解法的时间复杂度也是O（n），空间复杂度是O（1）。

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

分析

直接的想法是：左指针指向开始，右指针不断向后移动，如果右指针此时指向的字符没有出现过。则将它记录在哈希表里，并更新最长子串长度。如果右指针此时指向的字符出现过，就需要将左指针移动，移动到什么位置，移动到和右指针所指字符相同的字符的后面一个位置，这个位置也需要记录。同时将这个字符的下标修改为当前右指针所指位置。使用unordered_map<char,int>来记录某个字符曾经出现的位置，如果没有出现过，即 if(dict.count('某个字符')==0)。

代码

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        // 处理边界条件
        if(n == 0){
            return 0;
        }
        // 存储字符-下标的哈希表
        unordered_map<char,int> hash;
        // 最大长度
        int maxLen = 0;
        // 双指针解法
        for(int i=0,j=0; j < n;j++){
            // j所指字符没有在之前出现过
            if(hash.count(s[j]) == 0){
                // 更新哈希表
                hash[s[j]] = j;
                // 更新最大子串长度
                int curLen = j - i + 1;
                if(curLen > maxLen){
                    maxLen = curLen;
                }
                // 然后j继续向右移动即可
            }
            // j所指字符之前出现过
            else{
                // 更新i指针位置为先前出现的位置+1
                // i = hash[s[j]] + 1;
                // 上一行更新i的代码有逻辑错误，假如s="tmmzuxt"，
                // 此时i=2指向第二个m,j=6指向t，虽然t出现过,
                // 但i在第一个t后面的位置，所以不需要更新i,
                // 但是这里还要更新最大长度
                i = i > hash[s[j]] ? i : hash[s[j]]+1;
                int curLen = j - i + 1;
                if(curLen > maxLen){
                    maxLen = curLen;
                }
                // 更新哈希表
                hash[s[j]] = j;
            }
        }
        return maxLen;
    }
};

复杂度分析

使用了双指针来遍历整个字符串，其中一个指针 i 指向当前子串的起始位置，另一个指针 j 则用来遍历字符串，整个遍历过程的时间复杂度为 O(n)，其中 n 是输入字符串的长度。unordered_map 的count 方法时间复杂度为O(1)。整个算法的时间复杂度为 O(n)，其中 n 是输入字符串的长度。哈希表的空间复杂度是 O(n)。

LCR017.最小覆盖子串

代码

class Solution {
public:
    bool checkNum(unordered_map<char,int> hash){
        for(unordered_map<char,int>::iterator iter=hash.begin();iter != hash.end();iter++){
            if(iter->second > 0){
                return false;
            }
        }
        return true;
    }
     string minWindow(string s, string t) {
        // 哈希表存储字符-出现次数
        unordered_map<char,int> hash;
        // 结果字符串
        int minLen = INT_MAX;
        string res = "";
        // 记录字符串t的情况
        for(int i = 0;i < t.length();i++){
            hash[t[i]]++;
        }
        // 双指针遍历字符串s
        int left = 0, right = 0;
        int tLen = t.length();
        while (right < s.length()) {
            // 右指针向右移动，更新 hash 表
            if (hash.find(s[right]) != hash.end()) {
                hash[s[right]]--;
            }
            right++;

            // 当满足条件时，移动左指针
            while (checkNum(hash) && left < right) {
                if (right - left < minLen) {
                    minLen = right - left;
                    res = s.substr(left, minLen);
                }
                // 移动左指针，并更新 hash 表
                if (hash.find(s[left]) != hash.end()) {
                    hash[s[left]]++;
                }
                left++;
            }
        }
        return res;
    }
};

分析

同样使用双指针，如果没有完全包含字符串t，就向右移动右指针；如果已经包含，就向右移动左指针。如何判断是否包含，使用哈希表存储字母出现的次数，对于t中存在的字符，需要-1，不存在的字符可以忽略不计。

复杂度分析

这个算法的时间复杂度主要取决于双指针的遍历过程。假设字符串 s 的长度为 n，字符串 t 的长度为 m。

初始化哈希表的时间复杂度为 O(m)，因为需要遍历字符串 t 并统计每个字符的出现次数。
双指针遍历字符串 s 的时间复杂度为 O(n)。在最坏情况下，右指针会移动 n 次，而左指针也会移动 n 次。
在双指针的遍历过程中，对哈希表的更新操作是常数时间的，因此不影响总体时间复杂度。

综上所述，该算法的时间复杂度为 O(n + m)。

总结

双指针初始化： 在处理字符串的问题中，通常需要使用两个指针来构建一个窗口或者子串，其中一个指针用于标识子串的起始位置，另一个指针用于标识子串的结束位置。这两个指针的初始化通常在字符串的开头位置。

哈希表的应用： 为了有效地处理字符出现的次数或者其他相关信息，我们通常会利用哈希表来存储字符及其出现的次数。这样可以在 O(1) 的时间复杂度内快速查询、更新字符出现的次数。

滑动窗口的移动： 在双指针的框架下，窗口通常会向右滑动。右指针会向右移动，扩大窗口的大小，而左指针则会根据题目要求选择是否移动，以保持窗口的特性。

条件判断： 在窗口滑动的过程中，需要根据题目的要求不断进行条件判断。这些条件判断通常涉及到对哈希表的查询和更新，以及子串的特性判断等。