最短子字符串问题c++实现

最短子字符串问题可以用滑动窗口算法来解决。以下是一个C++实现示例：

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

string minWindow(string s, string t) {
    unordered_map<char, int> map;
    for (char c : t) {
        ++map[c];
    }
    int counter = map.size();
    int begin = 0, end = 0;
    int len = INT_MAX;
    string res = "";
    while (end < s.size()) {
        char c = s[end];
        if (map.find(c) != map.end()) {
            --map[c];
            if (map[c] == 0) {
                --counter;
            }
        }
        ++end;
        while (counter == 0) {
            char tempc = s[begin];
            if (map.find(tempc) != map.end()) {
                ++map[tempc];
                if (map[tempc] > 0) {
                    ++counter;
                }
            }
            if (end - begin < len) {
                len = end - begin;
                res = s.substr(begin, len);
            }
            ++begin;
        }
    }
    return res;
}

int main() {
    string s = "ADOBECODEBANC";
    string t = "ABC";
    cout << minWindow(s, t) << endl;
    return 0;
}

该实现使用了一个哈希表来记录目标字符串中每个字符出现的次数，使用begin和end两个指针来表示滑动窗口的左右边界，使用counter变量来记录目标字符串中还未匹配的字符数。在每次移动end指针时，检查当前字符是否在目标字符串中出现，如果出现则将其出现次数减1，如果该字符的出现次数减为0，则将counter减1。在每次移动begin指针时，检查当前字符是否在目标字符串中出现，如果出现则将其出现次数加1，如果该字符的出现次数大于0，则将counter加1。在每次移动begin指针时，还需要判断当前窗口是否为最短子字符串，如果是，则更新len和res变量。最终返回最短子字符串res即可。