# 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
-
n
-
height[i]
# 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;
}
时间复杂度:,其中 是数组 height
的长度
空间复杂度:
# 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: 双指针
初始时两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和,并和目标值比较:
- 如果两个元素之和等于目标值,则发现了唯一解。
- 如果两个元素之和小于目标值,则将左侧指针右移一位。
- 如果两个元素之和大于目标值,则将右侧指针左移一位。
移动指针之后,重复上述操作,直到找到答案。
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};
}
时间复杂度: ,其中 是数组的长度。两个指针移动的总次数最多为 次
空间复杂度:
# 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};
}
时间复杂度:,其中 是数组的长度
- 需要遍历数组一次确定第一个数,时间复杂度是
- 寻找第二个数使用二分查找,时间复杂度是
空间复杂度:
题解:推荐使用双指针方法
# 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]
提示:
-
nums.length
-
nums[i]
-
k
进阶:
- 尽可能想出更多的解决方案,至少有 三种 不同的方法可以解决这个问题。
- 你可以使用空间复杂度为 的 原地 算法解决这个问题吗?
# 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]
提示:
-
nums.length
-
nums[i]
进阶:你能尽量减少完成的操作次数吗?
# 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;
}
# 复杂度分析
时间复杂度:,其中 为字符串 s
的长度
空间复杂度:,其中, 为字符集的大小
# 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
提示:
-
s1.length
,s2.length
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;
}
时间复杂度: ,其中 是字符串 s1
的长度, 是字符串 s2
的长度, 是字符集,这道题中的字符集是小写字母,
空间复杂度:
# 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;
}
时间复杂度: ,创建 cnt
需要 的时间。遍历 s1
需要 的时间。双指针遍历 s2
时,由于 left
和 right
都只会向右移动,故这一部分需要 的时间
空间复杂度:
# 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
-
n
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++;
}
}
}
时间复杂度:,其中 是数组 nums 的长度
空间复杂度:
# 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++;
}
}
}
时间复杂度:,其中 是数组 nums 的长度
空间复杂度:
参考: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 <= 105
- s 和 t 由英文字母组成
进阶:你能设计一个在 时间内解决此问题的算法吗?
# 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;
}
时间复杂度:,其中, 和 分别是字符串 s 和 t 的长度
- 遍历字符串 t 的时间复杂度为
- 遍历字符串 s 的时间复杂度为 ,其中,最坏情况下,指针 l 和 r 各遍历一次字符串 s
- 哈希查找的时间复杂度为
空间复杂度:,其中, 为字符集的大小(即,字符串 t 中字符的种类数,对应于程序中的 k )
参考:
- leetcode-solution
- 林小鹿