# LeetCode 11. 盛最多水的容器

11. Container With Most Water

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例 1：

输入：height = [1,8,6,2,5,4,8,3,7]
输出：49
解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2：

输入：height = [1,1]
输出：1

提示：

• n == height.length
• $2 \le$ n $\le 10^5$
• $0 \le$ height[i] $\le 10^4$

# Method: 双指针

算法思路：

定义指针 i 和 j ，分别指向水槽的左右边界

水槽的容积由短板决定，即，水槽容积为 (j - i) * min(height[i], height[j])

在每个状态下，无论长板或短板向中间收窄一格，都会导致水槽的底边宽度变小：

• 若将短板向内侧移动， min(height[i], height[j]) 可能会变大，因此，下个水槽的容积可能会增大
• 若将长板向内侧移动， min(height[i], height[j]) ​ 不变或者会变小，因此，下个水槽的容积一定变小

因此，可以令双指针分别指向 height 的首尾，每次将短板向内侧移动一格，更新最大容积，直到两指针相遇时循环结束，即可获得最大容积

代码实现：

int maxArea(vector<int>& height) {

    int i = 0;

    int j = height.size() - 1;

    int res = 0;

    while (i < j) {

        if (height[i] <= height[j]) {

            res = max(res, (j - i) * height[i]);

            i++;

        } else {

            res = max(res, (j - i) * height[j]);

            j--;

        }

    }

    return res;

}

时间复杂度：$O(n)$，其中 $n$ 是数组 height 的长度

空间复杂度：$O(1)$

# LeetCode 167. 两数之和 II - 输入有序数组

LeetCode 167

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2 。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2]

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

# Method 1: 双指针

初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较：

1. 如果两个元素之和等于目标值，则发现了唯一解。
2. 如果两个元素之和小于目标值，则将左侧指针右移一位。
3. 如果两个元素之和大于目标值，则将右侧指针左移一位。

移动指针之后，重复上述操作，直到找到答案。

vector<int> twoSum(vector<int>& numbers, int target) {

    int i = 0, j = numbers.size() - 1;

    while (i < j)

    {

        if (numbers[i] == target - numbers[j])

            return {i + 1, j + 1};

        else if (numbers[i] < target - numbers[j])

            i++;

        else

            j--;

    };

    return {-1, -1};

}

时间复杂度：$O(n)$ ，其中 $n$ 是数组的长度。两个指针移动的总次数最多为 $n$ 次

空间复杂度：$O(1)$

# Method 2: 二分查找

在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。

vector<int> twoSum(vector<int>& numbers, int target) {

    for (int i = 0; i < numbers.size(); ++i) {

        int low = i + 1, high = numbers.size() - 1;

        while (low <= high) {

            int mid = (high - low) / 2 + low;

            if (numbers[mid] == target - numbers[i]) {

                return {i + 1, mid + 1};

            } else if (numbers[mid] > target - numbers[i]) {

                high = mid - 1;

            } else {

                low = mid + 1;

            }

        }

    }

    return {-1, -1};

}

时间复杂度：$O(n \log{n})$，其中 $n$ 是数组的长度

• 需要遍历数组一次确定第一个数，时间复杂度是 $O(n)$
• 寻找第二个数使用二分查找，时间复杂度是 $O(\log{n})$

空间复杂度：$O(1)$

题解：推荐使用双指针方法

# LeetCode 189. 轮转数组

LeetCode 189. Rotate Array

给定一个整数数组 nums ，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1：

输入：nums = [1,2,3,4,5,6,7], k = 3
输出：[5,6,7,1,2,3,4]
解释：
    向右轮转 1 步: [7,1,2,3,4,5,6]
    向右轮转 2 步: [6,7,1,2,3,4,5]
    向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2：

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释：
    向右轮转 1 步: [99,-1,-100,3]
    向右轮转 2 步: [3,99,-1,-100]

提示：

• $1 \le$ nums.length $\le 10^5$
• $-2^{31} \le$ nums[i] $\le 2^{31} - 1$
• $0 \le$ k $\le 10^5$

进阶：

• 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
• 你可以使用空间复杂度为 $O(1)$ 的 原地 算法解决这个问题吗？

# Method 1: 使用额外的数组

当我们将数组的元素向右移动 k 次后，尾部 k mod n 个元素会移动至数组头部，其余元素向后移动 k mod n 个位置。

使用额外的数组来将每个元素放至正确的位置。用 n 表示数组的长度，我们遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i + k) mod n 的位置，最后将新数组拷贝至原数组即可

void rotate(vector<int>& nums, int k) {

    int n = nums.size();

    vector<int> temp(n);

    for (int i = 0; i <= n - 1; i++)

        temp[(i + k) % n] = nums[i];

    nums.assign(temp.begin(), temp.end());

}

# Method 2: 数组翻转

先将所有元素翻转，这样尾部的 k mod n 个元素就被移至数组头部，然后我们再翻转 [0, k mod n − 1] 区间的元素和 [k mod n, n − 1] 区间的元素即能得到最后的答案

// 水平翻转 nums 中 left 到 right 之间的元素

void reverse(vector<int>& nums, int left, int right) {

    while (left < right)

    {

        swap(nums[left], nums[right]);

        left++;

        right--;

    };

}

void rotate(vector<int>& nums, int k) {

    int n = nums.size() - 1;

    reverse(nums, 0, n);                      // 翻转第 0 至 nums.size ()-1 个元素

    reverse(nums, 0, (k % nums.size()) - 1);  // 翻转第 0 至 k% nums.size ()-1 个元素

    reverse(nums, (k % nums.size()), n);      // 翻转第 k% nums.size () 至 nums.size ()-1 个元素

}

# LeetCode 283. 移动零

LeetCode 283. Move Zeroes

给定一个数组 nums ，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

示例 1：

输入：nums = [0,1,0,3,12]
输出：[1,3,12,0,0]

示例 2：

输入：nums = [0]
输出：[0]

提示：

• $1 \le$ nums.length $\le 10^4$
• $-2^{31} <=$ nums[i] $\le 2^{31} - 1$

进阶：你能尽量减少完成的操作次数吗？

# Method: 双指针

算法思路：

使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部

右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移

因此，每次交换都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变

代码实现：

void moveZeroes(vector<int>& nums) {

    int left = 0;

    for (int right = 0; right < nums.size(); ++right) {

        if (nums[right]) {

            swap(nums[left], nums[right]);

            ++left;

        }

    }

}

或者：

void moveZeroes(vector<int>& nums) {

    int left = 0;

    for (int right = 0; right < nums.size(); ++right) {

        if (nums[right]) {

            nums[left] = nums[right];

            ++left;

        }

    }

    for (; left < nums.size(); ++left) {

        nums[left] = 0;

    }

}

参考：leetcode-solution

# LeetCode 3. 无重复字符的最长子串

3. Longest Substring Without Repeating Characters

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1：

输入：s = "abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2：

输入：s = "bbbbb"
输出：1
解释：因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3：

输入：s = "pwwkew"
输出：3
解释：因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

# Method: 滑动窗口

# 算法思路

使用两个指针表示字符串中的某个子串（或窗口）的左右边界，该窗口容纳无重复字符的子串

分别定义 left 和 right 作为滑动窗口的左端点和右端点（初始化为 0 ），定义一个 unordered_set 对象 hash 来记录滑动窗口内的元素，利用 ans 记录窗口的最大长度（即，目标值）

向右移动 right ：

• 若窗口内不存在 s[right] 字符（即， hash.find(s[right]) != hash.end() ），可直接将 s[right] 放入窗口
• 若窗口内已经存在 s[right] 字符，需移动 left ，将窗口内已有的 s[right] 字符及其左侧字符全都移除出去，然后再将 s[right] 放入窗口
• 计算窗口的长度，即， right - left + 1 ，并将其与 ans 比较，以更新最大窗口长度

# 代码实现

int lengthOfLongestSubstring(string s) {

    unordered_set<char> hash;                       // 记录滑动窗口内的元素

    int left = 0;

    int right = 0;

    int ans = 0;

    while (right < s.size()) {

        while (hash.find(s[right]) != hash.end()) { //s [right] 在窗口内

            hash.erase(s[left]);

            ++left;

        }

        hash.insert(s[right]);                      // 将 s [right] 加入窗口

        ans = max(ans, right - left + 1);           // 更新滑动窗口的最大长度

        ++right;

    }

    return ans;

}

# 复杂度分析

时间复杂度：$O(n)$，其中 $n$ 为字符串 s 的长度

空间复杂度：$O(\vert \Sigma \vert)$，其中，$\vert \Sigma \vert$ 为字符集的大小

# LeetCode 567. 字符串的排列

LeetCode 567. Permutation in String

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说， s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab", s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba")

示例 2：

输入：s1 = "ab", s2 = "eidboaoo"
输出：false

提示：

• $1 \le$ s1.length , s2.length $\le 10^4$
• s1 和 s2 仅包含小写字母

# Method 1: 滑动窗口

两个字符串经过排序之后相等，可以说明一个字符串是另一个的排列。（时间复杂度高）

只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列

记 s1 的长度为 n ，可以遍历 s2 中每个长度为 n 的子串，判断子串和 s1 中每个字符的个数是否相等，若相等则说明该子串是 s1 的一个排列

数组 cnt1 统计 s1 中各个字符的个数， cnt2 统计当前遍历的子串中各个字符的个数

由于需要遍历的子串长度均为 n ，可以使用一个固定长度为 n 的滑动窗口来维护 cnt2 ：滑动窗口每向右滑动一次，就多统计一次进入窗口的字符，少统计一次离开窗口的字符。然后，判断 cnt1 ​ 是否与 cnt2 ​相等，若相等则意味着 s1 的排列之一是 s2 的子串。

bool checkInclusion(string s1, string s2) {

    int n1 = s1.size(), n2 = s2.size();

    if (n1 > n2) return false;

    vector<int> cnt1(26),cnt2(26);

    for (int i = 0; i < n1; i++) {  // 统计 s1 每个字符的出现次数，s2 中首个长为 n1 子串每个字符的出现次数

        ++cnt1[s1[i] - 'a'];

        ++cnt2[s2[i] - 'a'];

    }

    if (cnt1 == cnt2) return true;

    for (int i = n1; i < n2; i++) { // 滑动窗口法（窗长为 n1），更新窗口内每个字符的出现次数

        ++cnt2[s2[i] - 'a'];        // 进入窗口的字符

        --cnt2[s2[i- n1] - 'a'];    // 离开窗口的字符

        if (cnt1 == cnt2) return true;

    }

    return false;

}

# Method 2: 滑动窗口

注意到每次窗口滑动时，只统计了一进一出两个字符，却比较了整个 cnt1 和 cnt2 数组。因此可对上述算法进行优化：用一个变量 diff 来记录 cnt1 与 cnt2 的不同值的个数，这样判断 cnt1 和 cnt2 是否相等就转换成了判断 diff 是否为 0

为简化上述逻辑，可以只用一个数组 cnt ，其中 cnt[x]=cnt2[x]−cnt1[x] ，将 cnt1[x] 与 cnt2[x] 的比较替换成 cnt[x] 与 0 的比较

bool checkInclusion(string s1, string s2) {

    int n1 = s1.size(), n2 = s2.size();

    if (n1 > n2) return false;

    // 数组 cnt 记录的是 s1 字符串与 s2 窗口中，每个字符出现次数的差异值：若 cnt1 cnt2 分别记录 s1 字符串与 s2 窗口中每个字符出现次数，则 cnt=cnt2-cnt1

    vector<int> cnt(26);        //s1 s2 仅包含小写字母

    for (int i = 0; i < n1; i++) {

        --cnt[s1[i] - 'a'];

        ++cnt[s2[i] - 'a'];

    }

    int diff = 0;               // 记录 cnt 非零元素的个数，即，cnt1 与 cnt2 不相等元素的个数

    for (auto c : cnt)

        if (c != 0)

            ++diff;

    if (diff == 0) return true; //diff 等于 0，即 cnt1 与 cnt2 相同，输出 true

    for (int i = n1; i < n2; i++) {

        int x = s2[i] - 'a', y = s2[i - n1] - 'a'; //x 对应进入窗口的字符，y 对应离开窗口的字符

        if (x == y) continue;           //x 等于 y 时，无需修改 cnt 和 diff

        if (cnt[x] == 0) ++diff;        //cnt1 [x] 原本等于 cnt2 [x]，新进入的 x 导致 diff 加 1

        ++cnt[x];

        if (cnt[x] == 0) --diff;        // 进入窗口的 x 使得 cnt1 [x] 等于 cnt2 [x]，故 diff 减 1（该 if 语句是上一条 if 语句是互斥的）

        if (cnt[y] == 0) ++diff;

        --cnt[y];

        if (cnt[y] == 0) --diff;

        if (diff == 0) return true;

    }

    return false;

}

时间复杂度：$O(n + m + \vert \Sigma \vert)$ ，其中 $n$ 是字符串 s1 的长度，$m$ 是字符串 s2 的长度，$\Sigma$ 是字符集，这道题中的字符集是小写字母，$\vert \Sigma \vert =26$

空间复杂度：$O(\vert \Sigma \vert)$

# Method 3: 双指针

方法一的思路：在保证区间长度为 n 的情况下，去考察是否存在一个区间使得 cnt 的值全为 0 。反过来，还可以在保证 cnt 的值不为正的情况下，去考察是否存在一个区间，其长度恰好为 n

初始时，仅统计 s1 中的字符，则 cnt 的值均不为正，且元素值之和为 - n

用指针 left 和 right 表示考察的区间 [left,right] 。 right 每向右移动一次，就统计一次进入区间的字符 x 。为保证 cnt 的值不为正，若此时 cnt[x] > 0 ，则向右移动左指针，减少离开区间的字符的 cnt 值直到 cnt[x] ≤ 0

注意到 [left,right] 的长度每增加 1 ， cnt 的元素值之和就增加 1 。当 [left,right] 的长度恰好为 n 时，就意味着 cnt 的元素值之和为 0 。由于 cnt 的值不为正，元素值之和为 0 就意味着所有元素均为 0 ，这样我们就找到了一个目标子串

bool checkInclusion(string s1, string s2) {

    int n1 = s1.size(), n2 =s2.size();

    if (n1 > n2) return false;

    vector<int> cnt(26);

    for (int i = 0; i < n1; i++)

        --cnt[s1[i] - 'a'];     //cnt 的元素值之和为 - n1

    int l = 0;

    // 在保证 cnt 的值不为正（所有元素均不为正）的情况下，去考察是否存在一个区间，其长度恰好为 n1

    for (int r = 0; r < n2; r++) {

        int x = s2[r] - 'a';

        ++cnt[x];

        while (cnt[x] > 0) { //x 出现次数多，l 右移，并更新 cnt

            --cnt[s2[l] - 'a'];

            ++l;

        }

        if (r - l + 1 == n1) return true;   //cnt 各元素均不为正，且区间 [l,r] 长度刚好为 n1，找到目标

    }

    return false;

}

时间复杂度：$O(n + m + \vert \Sigma \vert)$ ，创建 cnt 需要 $O(\vert \Sigma \vert)$ 的时间。遍历 s1 需要 $O(n)$ 的时间。双指针遍历 s2 时，由于 left 和 right 都只会向右移动，故这一部分需要 $O(m)$ 的时间

空间复杂度：$O(\vert \Sigma \vert)$

# LeetCode 75. 颜色分类

75. Sort Colors

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

提示：

• n == nums.length
• $1 \le$ n $\le 300$
• nums[i] 为 0 、 1 或 2

进阶：你能想出一个仅使用常数空间的一趟扫描算法吗？

# 思路

可以先统计数组中 0, 1, 2 的个数，再根据它们的数量修改整个数组

但是，这样需要遍历两次

为实现一次遍历，可定义双指针，实现原地交换

考虑以下两种方案：

• ptr0 指向 0 的填充位置，ptr1 指向 1 的填充位置
• ptr0 指向 0 的填充位置，ptr2 指向 2 的填充位置

# Method 1：双指针

算法思路：

定义指针 ptr0 指向 0 的填充位置，ptr1 指向 1 的填充位置

[0, ptr0) 区间内的元素全为 0 ，[ptr0, ptr1) 区间内的元素全为 1

初始化 ptr0 为 0 ，初始化 ptr1 为 0

从左往右遍历数组，记遍历到的位置为 i（i 从 0 开始）：

• 如果 nums [i] == 0 ，交换 nums [i] 与 nums [ptr0] ，并做以下考虑：

  • 如果 ptr1 > ptr0 ，交换前的 nums [ptr0] 必定为 1 ，即，交换后的 nums [i] 为 1 ，此时，还需将 nums [i] 与 nums [ptr1] 进行交换（因为 [ptr1, i) 区间对应的元素值全为 2 ）
  • 无论 ptr1 > ptr0 是否成立，都需将 ptr0 和 ptr1 向右移动一位、将 i 向右移动一位

• 如果 nums [i] == 1 ，交换 nums [i] 与 nums [ptr1] ，并将 ptr1 向右移动一位、将 i 向右移动一位

代码实现：

void sortColors(vector<int>& nums) {

    int ptr0 = 0;

    int ptr1 = 0;

    for (int i = 0; i < nums.size(); i++) {

        if (nums[i] == 0) {

            swap(nums[i], nums[ptr0]);

            if (ptr0 < ptr1) {

                swap(nums[i], nums[ptr1]);

            }

            ptr0++;

            ptr1++;

        } else if (nums[i] == 1) {

            swap(nums[i], nums[ptr1]);

            ptr1++;

        }

    }

}

时间复杂度：$O(n)$，其中 $n$ 是数组 nums 的长度

空间复杂度：$O(1)$

# Method 2：双指针

算法思路：

定义指针 ptr0 指向 0 的填充位置，ptr2 指向 2 的填充位置

[0, ptr0) 区间内的元素全为 0 ，(ptr2, nums.size () - 1] 区间内的元素全为 2

初始化 ptr0 为 0 ，初始化 ptr2 为 nums.size () - 1

从左往右遍历数组，记遍历到的位置为 i（i 从 0 开始），当 i 超过 ptr2 时，结束遍历：

• 如果 nums [i] == 0 ，交换 nums [i] 与 nums [ptr0] ，并将 ptr0 向右移动一位、将 i 向右移动一位

• 如果 nums [i] == 2 ，交换 nums [i] 与 nums [ptr2] ，并将 ptr2 向左移动一位，但是，交换所得的 nums [i] 可能是 0 、1、2 中的任意值，需要继续对 nums [i] 进行判断和处理

• 如果 nums [i] == 1 ，无需进行任何交换，直接将 i 右移一位即可

当 nums [i] == 0 时，可以在交换 nums [i] 与 nums [ptr0] 以后直接将 i 右移，无需考虑交换后 nums [i] 的取值，这是因为：

• 若 i == ptr0 ，实际并未进行交换，新的 nums [i] 就是 0
• 若 i > ptr0 ，由于 i 是从左往右遍历的，区间 [ptr0, i - 1] 对应的元素值必定全为 1 ，在交换 nums [i] 与 nums [ptr0] 以后，区间 [0, ptr0] 对应的元素值全为 0 、区间 [ptr0 + 1, i] 对应的元素值全为 1 ，因此，可以直接考虑 i + 1 位置

特别地：当 nums [i] == 2 时，需要将其与 nums [ptr2] 进行交换，由于交换后的 nums [i] 可能是 0 ，即，需要再按照 nums [i] == 0 的情况进行处理。因此，在遍历 nums [i] 时， 我们可以先处理 nums [i] == 2 的情况，再处理 nums [i] == 0 的情况，以简化代码

代码实现：

void sortColors(vector<int>& nums) {

    int ptr0 = 0;

    int ptr2 = nums.size() - 1;

    for (int i = 0; i <= ptr2; i++) {

        while (i <= ptr2 && nums[i] == 2) {

            swap(nums[i], nums[ptr2]);

            ptr2--;

        }

        if (nums[i] == 0) {

            swap(nums[i], nums[ptr0]);

            ptr0++;

        }

    }

}

时间复杂度：$O(n)$，其中 $n$ 是数组 nums 的长度

空间复杂度：$O(1)$

参考：leetcode-solution

# LeetCode 76. 最小覆盖子串

76. Minimum Window Substring

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

示例 2：

输入：s = "a", t = "a"
输出："a"
解释：The entire string s is the minimum window.

示例 3：

输入：s = "a", t = "aa"
输出：""
解释：Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

提示：

• m == s.length
• n == t.length
• 1 <= m, n <= 10⁵
• s 和 t 由英文字母组成

进阶：你能设计一个在 $O(m + n)$ 时间内解决此问题的算法吗？

# Method 1: 滑动窗口法 + 哈希

算法思路：

本题要在字符串 s 中找到一个包含字符串 t 全部字符的最小窗口

为便于表述，我们做出以下规定：

• 若窗口包含字符串 t 全部字符，则该窗口为「可行窗口」
• 若窗口内某个字符的数量 大于等于 字符串 t 中该字符的数量，则称该字符为「达标字符」

可以用滑动窗口的思想来求解：

• 移动窗口的右端点（ r 指针），不断扩张窗口
• 当窗口为「可行窗口」时，移动窗口的左端点（ l 指针），收缩窗口
• 通过在字符串 s 上移动窗口，获取长度最小的「可行窗口」

为判断当前窗口是否为「可行窗口」，我们做以下考虑：

• 定义一个哈希表，unordered_map<char, int> hash ，其中，以 t 中字符作为哈希表的键，以 窗口内该字符的数量 与 t 中该字符的数量 之差作为对应的值（例如，当窗口内字符 'a' 出现 1 次、t 中字符 'a' 出现 2 次时，对应哈希表的值 hash ['a'] 为 -1）
• 如果某个字符对应的哈希表键值等于 0 ，则说明这个字符为「达标字符」
• 定义 cnt 表示窗口内「达标字符」的个数，定义 k 表示字符串 t 中的字符种类数（即，k = hash.size () ）
• 若 cnt 等于 k ，说明当前窗口包含了字符串 t 中的全部字符，即，当前窗口为「可行窗口」

代码实现：

string minWindow(string s, string t) {

    unordered_map<char, int> hash;

    for (auto c : t) hash[c]--;     //hash [c] 表示 窗口中字符 c 的数量与 t 中字符 c 的数量之差

    int k = hash.size();            //t 中字符的类别数

    string ans;

    int cnt = 0;                    // 在窗口内，满足 t 字符串所需数量要求的字符个数

    for (int l = 0, r = 0; r < s.size(); r++) {

        hash[s[r]]++;

        if (hash[s[r]] == 0) cnt++; //s [r] 字符的数量已满足要求

        while (hash[s[l]] > 0) {    // 在确保 s [l] 满足数量要求的前提下，收缩窗口

            hash[s[l]]--;           //s [l] 字符数量减 1

            l++;                    //l 右移

        }

        if (cnt == k) {             // 窗口包含 t 所有字符

            if (ans.empty() || r - l + 1 < ans.size()) {

                ans = s.substr(l, r - l + 1);

            }

        }

    }

    return ans;

}

时间复杂度：$O(m + n)$，其中，$m$ 和 $n$ 分别是字符串 s 和 t 的长度

• 遍历字符串 t 的时间复杂度为 $O(n)$
• 遍历字符串 s 的时间复杂度为 $O(m)$，其中，最坏情况下，指针 l 和 r 各遍历一次字符串 s
• 哈希查找的时间复杂度为 $O(1)$

空间复杂度：$O(\vert \Sigma \vert)$，其中，$\vert \Sigma \vert$ 为字符集的大小（即，字符串 t 中字符的种类数，对应于程序中的 k ）

参考：

• leetcode-solution
• 林小鹿