一、最小覆盖子串

解法:哈希表匹配

字符串仅包含大小写字母，则字符集是已知且有限的，那这种情况下我们可以考虑快速查找某个元素是否出现过的哈希表——只需要维护一个哈希表，将字符串T中的字符作为key值，初始化时当字符在T中出现一次则对应的value值减1：

for(int i = 0; i < T.length(); i++)
    //初始化哈希表都为负数，找的时候再加为正
    hash[T.charAt(i)] -= 1; 

1
2
3
4

后续如果在字符串S中找到相应字符就可以将其加回来:

char c = S.charAt(fast);
//目标字符匹配+1
hash[c]++;

1
2
3
4

然后使用双指针维护滑动窗口，在窗口内，哈希表中value都大于0：

for (int i = 0; i < hash.length; i++) {
    if (hash[i] < 0)
        return false;
}
return true;

1
2
3
4
5
6

这个窗口内出现了T中所有的字符串，此时可以尝试缩小窗口，因为双指针同步向右遍历，因此缩小窗口只能是缩小左界。

• 建立哈希表，遍历字符串T，统计各个字符出现的频率，频率计为负数。
• 依次遍历字符串S，如果匹配则将哈希表中的相应的字符加1。
• 在遍历过程中维护一个窗口，如果哈希表中所有元素都大于0，意味着已经找全了，则窗口收缩向左移动，找最小的窗口，如果不满足这个条件则窗口右移继续匹配。窗口移动的时候需要更新最小窗口，以取得最短子串。
• 如果匹配到最后，窗口left（初始为-1）也没有右移，说明没有找到，返回空串即可。
• 最后使用字符串截取函数，截取刚刚记录下的窗口即可得到符合条件的最短子串。
  

class Solution {
public:
    //检查是否有小于0的
    bool check(unordered_map<char, int> &hash) { 
        for (auto iter = hash.begin(); iter != hash.end(); iter++) {
            if (iter->second < 0)
                return false;
        }
        return true;
    }
    string minWindow(string S, string T) {
        int cnt = S.length() + 1;
        //记录目标字符串T的字符个数
        unordered_map<char, int> hash; 
        for(int i = 0; i < T.length(); i++)
            //初始化哈希表都为负数，找的时候再加为正
            hash[T[i]] -= 1; 
        int slow = 0, fast = 0;  
        //记录左右区间
        int left = -1, right = -1;  
        for(; fast < S.length(); fast++){
            char c = S[fast];
            //目标字符匹配+1
            if(hash.count(c))    
            hash[c]++;
            //没有小于0的说明都覆盖了，缩小窗口
            while(check(hash)){   
                //取最优解
                if(cnt > fast - slow + 1){ 
                    cnt = fast - slow + 1;  
                    left = slow;
                    right = fast;
                }
                char c = S[slow];
                if(hash.count(c))
                    //缩小窗口的时候减1
                    hash[c]--; 
                //窗口缩小
                slow++;      
          }
      }
      //找不到的情况
      if (left == -1)     
          return "";
      return string(S.begin() + left, S.begin() + (right + 1));
  }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

时间复杂度：O(C∗nS+nT)其中C为T字符串的字符集大小，本题中为52个字母，nS为字符串S的长度，nT为字符串T的长度
空间复杂度：O©，哈希表长度不会超过字符串T的字符集大小

二、反转字符串

解法一:创建新串

开辟一个和str长度大小相同的一个字符串ans，把传入的str倒序赋值到ans字符串上

class Solution {
public:
    string solve(string str) {
        string ans = str;
        int len = str.length();
        for(int i = 0 ; i < len ;i++)
        {
                ans[i] = str[len-1-i];
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度:O(n)
空间复杂度:O(n)

解法二:原地反转

原地交换，str[i]=str[len-i-1],注意：交换进行的次数是len/2次

class Solution {
public:
    string solve(string str) {
        int len = str.length();
        for(int i = 0 ; i < len/2 ;i++)
        {
                swap(str[i],str[len-1-i]);
        }
        return str;
    }
};
1
2
3
4
5
6
7
8
9
10
11

时间复杂度:O(n)
空间复杂度:O(n)

解法三:库函数

class Solution {
public:
    string solve(string str) {
       reverse(str.begin(),str.end());
       return str;
    }
};
1
2
3
4
5
6
7

三、最长无重复子数组

解法:滑动窗口

既然要找一段连续子数组的内不重复的长度，我们可以使用滑动窗口，保证窗口内都是不重复的，然后窗口右界不断向右滑，如果窗口内出现了重复数组，说明新加入的元素与之前的重复了，只需要窗口左界也向右收缩就可以保证窗口内都是不重复的。

而保证窗口内的元素不重复，我们可以使用根据key值快速访问的哈希表，key值为窗口内的元素，value为其出现次数，只要新加入窗口的元素出现次数不为1，就是重复。

while(mp.get(arr[right]) > 1) 
    //窗口左移，同时减去该数字的出现次数
    mp.put(arr[left],mp.get(arr[left++])-1); 

1
2
3
4

• 构建一个哈希表，用于统计数组元素出现的次数。
• 窗口左右界都从数组首部开始，每次窗口优先右移右界，并统计进入窗口的元素的出现频率。
• 一旦右界元素出现频率大于1，就需要右移左界直到窗口内不再重复，将左边的元素移除窗口的时候同时需要将它在哈希表中的频率减1，保证哈希表中的频率都是窗口内的频率。
• 每轮循环，维护窗口长度最大值。
  

class Solution {
public:
    int maxLength(vector<int>& arr) {
        //哈希表记录窗口内非重复的数字
        unordered_map<int, int> mp; 
        int res = 0;
        //设置窗口左右边界
        for(int left = 0, right = 0; right < arr.size(); right++){ 
            //窗口右移进入哈希表统计出现次数
            mp[arr[right]]++; 
            //出现次数大于1，则窗口内有重复
            while(mp[arr[right]] > 1) 
                //窗口左移，同时减去该数字的出现次数
                mp[arr[left++]]--; 
            //维护子数组长度最大值
            res = max(res, right - left + 1); 
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：O(n)，外循环窗口右界从数组首右移到数组尾，内循环窗口左界同样如此，因此复杂度为O(n+n)=O(n)
空间复杂度：O(n)，最坏情况下整个数组都是不重复的，哈希表长度就为数组长度n