热题100 – 字串

针对连续子数组问题，通常有两种解法

1、滑动窗口解法，但是该解法只局限于数组中的值全体非负或非正

2、前缀和 （ + 哈希表 ）

题源一  560. 和为 K 的子数组 – 力扣（LeetCode）

算法思想： 前缀和 + 哈希表， 具体思路参考  – 前缀和 + 哈希表 |

问题关键在于怎样去统计 i < j , s[j] – s[i] = k 的个数

下列各方法时间复杂度均为 O(n) [都需要遍历一遍sum数组]

阿Q解决

s[j] = s[i] + k  ->   哈希表键s[i] + k

遍历一遍sum数组，查询当前的sum[i] 是否在哈希表中，并用哈希表记录 sum[i] + k 值的下标位置数组

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 前缀和数组
        vector<int> sum;
        sum.emplace_back(0);
        int n = nums.size();

        for(int i = 0; i < n; ++i)
            sum.emplace_back(sum.back() + nums[i]);

        // 找符合条件的子数组：i < j  s[j] - s[i] = k
        // 转换为 s[j] = s[i] + k -  枚举s[i]的值，并存入哈希表中
        unordered_map<int, vector<int>> mp;
        int ans = 0;

        for(int i = 0; i < n + 1; ++i){
            auto left = mp.find(sum[i]);
            if(left != mp.end())
                ans += left->second.size();
            mp[sum[i] + k].emplace_back(i - 1);  

        }
        return ans;
    }
};

/*
    出现的问题：
        在循环中是对sum数组进行相关操作，而非nums
    
    代码思想：
        前缀和解决对应的连续子数组问题
        由于需要满足 i < j， s[j] - s[i] = k， 从左到右遍历sum数组，查找当前的sum值是否在哈希表，并将 s[i] + k 加入哈希表内
*/

优化：由于题中不要求返回 子数组，因此哈希表的value 记录 sum[i] + k 的个数

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // 前缀和数组
        vector<int> sum;
        sum.emplace_back(0);
        int n = nums.size();

        for(int i = 0; i < n; ++i)
            sum.emplace_back(sum.back() + nums[i]);

        // 找符合条件的子数组：i < j  s[j] - s[i] = k
        // 转换为 s[j] = s[i] + k -  枚举s[i]的值，并存入哈希表中
        unordered_map<int, int> mp;
        int ans = 0;

        for(int i = 0; i < n + 1; ++i){
            auto left = mp.find(sum[i]);
            if(left != mp.end())
                ans += left->second;
            ++mp[sum[i] + k];  
        }
        return ans;
    }
};

/*
    出现的问题：
        在循环中是对sum数组进行相关操作，而非nums
    
    代码思想：
        前缀和解决对应的连续子数组问题
*/

官解

s[i] = s[j] – k   哈希表键s[i]

一遍枚举j，一边在 哈希表中 查找 s[j] – k 的数量

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // s[i] = s[j] - k 的方法
        // 两次遍历
        int n = nums.size();
        vector<int> sum(n + 1, 0);

        for(int i = 0; i < n; ++i)
            sum[i + 1] = sum[i] + nums[i];
        
        unordered_map<int, int> mp;
        int ans = 0;

        // 遍历sum数组 并查表
        for(const int& sj: sum){
            ans += (mp.contains(sj - k))? mp[sj - k]: 0;
            // cout << ans << endl;
            ++mp[sj]; 
        }
        return ans;
    }
};

 优化：可以将两次遍历合并到一起，一边枚举j，一边查表

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        // s[i] = s[j] - k 的方法
        unordered_map<int, int> mp;
        int ans = 0;

        // 一边枚举j，一边查表
        mp[0] = 1;   // 十分重要的初始化，类似于sum[0] = 0
        int sj = 0;

        for(const int& x: nums){
            sj += x;
            ans += (mp.contains(sj - k))?mp[sj - k]:0;
            ++mp[sj];
        }
        return ans;
    }
};

题源二  239. 滑动窗口最大值 – 力扣（LeetCode）

方法一   优先队列

class Solution {
public:
    //  优先队列解决
    //  优先队列设计默认最大值置顶
    //  pair比较内部已实现先比较第一个，再比较第二个
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();

        if(k > n) return vector<int>();

        vector<int> ans;

        priority_queue<pair<int, int>> q;

        for(int i = 0; i < n ; ++i){
            q.emplace(nums[i], i);

            // 若优先队列头部元素早已超出滑动窗口，则踢出优先队列
            while(i - q.top().second >= k)  q.pop();

            if(i >= k - 1) 
              ans.emplace_back(q.top().first); 
        }
        return ans;
    }
};

方法二   单调队列

思想：“裁员”广进

1、年轻能力不逊于年长员工，裁掉老员工

2、老员工岁数超过阈值，裁掉老员工

class Solution {
public:
    /*
        此题的难点在于
            每一个窗口内查找最值是没什么关系的，如何在`相邻滑动窗口间建立联系`是本题的难点

            使用 单调队列 从而解决问题
            
            思路 (“降本增效”):
                1、若新员工不逊于老员工，则将老员工裁掉
                2、若老员工35岁，也裁掉

    */
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        // 队列中存取下标
        deque<int> deq;

        vector<int> ans;

        int n = nums.size();

        for(int i = 0; i < n; ++i){
            // 入： 若新员工不逊于老员工，则将老员工裁掉
            while(!deq.empty() && nums[deq.back()] <= nums[i])
                deq.pop_back();
            deq.push_back(i);

            // 出：若老员工35岁，也裁掉
            if(i - deq.front() == k) deq.pop_front();

            if(i >= k - 1) ans.emplace_back(nums[deq.front()]);
        }
        return ans;
    }
};

方法三   分块 +  预处理（十分巧妙）

此思想阿Q第一次遇到，分块后的未越界部分由suffixMax决定（suffixMax的每一块都是从从右到左填最值）；越界部分由 prefixMax决定（prefixMax的每一块都是从左到右填最值）

最终的每个滑动窗口的最终为  max(suffixMax[i], prefixMax[i + k –  1])

class Solution {
public:
    // 分块 + 预处理
    /*
      有两种情况：

      1、如果 i 是 k 的倍数，那么 nums[i] 到 nums[i+k−1] 恰好是一个分组。我们只要预处理出每个分组中的最大值，即可得到答案；

      2、 如果 i 不是 k 的倍数，那么 nums[i] 到 nums[i+k−1] 会跨越两个分组，占有第一个分组的后缀以及第二个分组的前缀。
          假设 j 是 k 的倍数，并且满足 i<j≤i+k−1，那么 nums[i] 到 nums[j−1] 就是第一个分组的后缀，nums[j] 到 nums[i+k−1] 就是第二个分组的前缀。
          如果我们能够预处理出每个分组中的前缀最大值以及后缀最大值，同样可以在 O(1) 的时间得到答案
               
      【阿Q备注： 存在越界时，prefix处理越界的部分最值，suffix处理未越界部分的最值】
    */
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> prefixMax(n, 0);  
        vector<int> suffixMax(n, 0); 

        vector<int> ans;

        // prefixMaX预处理
        /* 
            prefixMax[i]有两种情况
            组头： prefixMax[i] = nums[i] 
            非组头：prefixMax[i] = max(prefixMax[i - 1], nums[i])
        */
        for(int i = 0; i < n; ++i){
          if( !(i % k) )  prefixMax[i] = nums[i];
          else prefixMax[i] = max(prefixMax[i - 1], nums[i]);
        }

        // suffixMax预处理
        /*
            suffixMax[i]也有两种情况
            组尾：prefixMax[i] = nums[i]
            非组尾：prefixMax[i] = max(prefixMax[i + 1], nums[i])
        */
        suffixMax[n - 1] = nums[n - 1];
        for(int i = n - 2; i > 0; --i){
            if( !((i + 1) % k) ) suffixMax[i] = nums[i];
            else suffixMax[i] = max(suffixMax[i  + 1], nums[i]);
        }

        // 滑动窗口
        for(int i = 0; i <= n - k; ++i){
            ans.emplace_back(max(suffixMax[i], prefixMax[i + k -1]));
        }
        
        return ans;
    }
};

题源三 76. 最小覆盖子串 – 力扣（LeetCode）

阿Q笨重的方法

此题阿Q起初用了十分杂糅的办法（收到滑动窗口解法的启发）

• 用tcount[128] 存取模式串各字符数量
• 先遍历一次主串，将在模式串中的字符用pair(char, int) 存入t_in_s数组中
• 使用滑动窗口解决匹配问题，记录各个符合匹配情况的子串字符数量，记录下最小字串长度的左右边界
• 返回 左右边界的 字符字串即可

class Solution {
public:
    /*
        思路：
          先遍历一次字符串，将符合要求的字符用pair(char, int) 存入数组中
          然后滑动窗口解决匹配问题，记录各个匹配情况的子串字符数量，最终返回结果
    */
    string minWindow(string s, string t) {
        int tsize = t.size(), ssize = s.size();
        if (tsize > ssize)
            return "";

        // 模式串字符数组记录数量
        vector<int> tcount(128);

        for (int i = 0; i < tsize; ++i)
            ++tcount[t[i]];

        // 遍历字符串， 存入模式串中存在的字符进入数组
        vector<pair<char, int>> t_in_x;

        for (int i = 0; i < ssize; ++i)
            if (tcount[s[i]])
                t_in_x.emplace_back(s[i], i);

        int n = t_in_x.size();

        // 在t_in_x数组中滑动窗口
        // diff 应该存取 t字符串中不同的字符数量
        int diff = 0;
        for(int i = 0; i < 128; ++i)
            if(tcount[i]) ++diff;

        cout << diff << endl;

        int minleft = -1, minright = -1;

        //  取最小值应该先存入最大值
        int minlen = INT_MAX;
        int right = 0;
        for (int left = 0; left < n; ++left) {
            // 右指针加值
            // 从不满足数量条件到满足
            while (diff && right < n) {
                if (tcount[t_in_x[right].first] == 1)
                    --diff;
                --tcount[t_in_x[right++].first];
            }

            if(right >= n && diff) break;

            if (!diff) {
                // 满足条件
                // 从满足条件到不满足条件
                if (tcount[t_in_x[left].first] == 0)
                    ++diff;
                ++tcount[t_in_x[left].first];

                if (minlen > t_in_x[right - 1].second - t_in_x[left].second + 1) {
                    minright = t_in_x[right - 1].second;
                    minleft = t_in_x[left].second;
                    minlen = minright - minleft + 1;
                    cout << minleft << "\t" << minright << "\t" << minlen << endl;
                }
            }
        }

        if (minright == -1)
            return "";
        return s.substr(minleft, minright - minleft + 1);
    }
};

/*
  出现的问题：
    1、diff 值应为 t字符串中不同字符的个数，而非 t.size()
    2、right始终指向的为出错(diff != 0 || right >= n)的下一个位置，因此 t_in_x 取下标 [right - 1] 而非 [right]
*/

此方法用时快要超时了，急需巧妙的方法去解决