LeetCode 76.最小覆盖子串题目链接:
https://leetcode-cn.com/problems/minimum-window-substring/
题目描述:
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
提示：
1. 1 <= s.length, t.length <= 105
2. s 和 t 由英文字母组成
题目分析:
这道题我们采用滑动窗口的思想，用l，r分别表示滑动窗口的左右边界，改变l，r来改变滑动窗口的大小。我们用数组need来存储当前滑动窗口中需要各个元素的数量，用字符串t初始化这个need数组。如果滑动窗口包含某个元素，我们就让need数组中同个元素的数量减一，反之加一。我们还需定义一个变量count存放需要的字符数，当遇到一个需要的元素就让这个变量减一，这样可以省下遍历数组need的步骤。首先，我们让左右边界都指向字符串第一个元素，增加r即右边界使滑动窗口增大，直到滑动窗口包含字符串t中的所有元素。然后再让左边界向右移动，缩小滑动窗口大小，使不必要的元素排除在滑动窗口外，直到遇到一个必须包含的元素，这个元素不能排除到滑动窗口外，此时记录此窗口。最后让左边界再右移一个位置，并让右边界右移，寻找下一个符合条件的滑动窗口，重复刚刚的寻找步骤。
题解:
执行用时: 4 ms
内存消耗: 38.5 MB
class Solution {
public String minWindow(String s, String t) {
// 定义变量存放字符串长度
int sLength = s.length();
int tLength = t.length();
// 如果其中一个字符串为空或者字符串s长度比字符串t长度还小
// 说明s中不存在涵盖t所有字符的子串，返回空字符串
if (sLength == 0 || tLength == 0 || sLength < tLength)
return "";
//记录需要的字符的个数
int[] need = new int[128];
// 用字符串t中各元素来初始化need
for (int i = 0; i < tLength; i++)
need[t.charAt(i)]++;
// l是当前左边界，r是当前右边界，size记录窗口大小，count是需求的字符个数，start是最小覆盖串开始的index
int l = 0, r = 0, size = sLength + 1, count = tLength, start = 0;
// 遍历字符串s
while (r < sLength) {
// 获取当前右边界字符
char c = s.charAt(r);
// 需要字符charArrayS[r]
if (need[c] > 0)
// 需求的字符个数减一
count--;
// 把右边的字符加入窗口，需要字符数减一
need[c]--;
// 当前窗口中已经包含t中所有字符
if (count == 0) {
while (need[s.charAt(l)] < 0) {
// 释放左边移动出窗口的字符
need[s.charAt(l)]++;
// 左指针右移
l++;
}
// 不能右移时候挑战最小窗口大小，更新最小窗口开始的start
if (r - l + 1 < size) {
size = r - l + 1;
// 记录下最小值时候的开始位置
start = l;
}
// 左边界向右移动后窗口肯定不能满足了，重新开始循环
need[s.charAt(l)]++;
// 左边界右移
l++;
// 需要字符数加一
count++;
}
// 右边界右移
r++;
}
// 返回结果字符串
return size == (sLength + 1) ? "" : s.substring(start, start + size);
}
}题目来源:力扣(LeetCode)