今天照例每日一题，然后麻溜的看题解，发现又是一道滑动窗口题。所以开个专题归类一下。
参考链接
基础算法精讲03-滑动窗口
👉️双指针的应用场景：
- 单调性
713.乘积小于K的子数组
给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。
提示:
- 1 <= nums.length <= 3 * 104
- 1 <= nums[i] <= 1000
- 0 <= k <= 106
解题思路
完整代码
3.无重复字符的最长子串
给定一个字符串s，请你找出其中不含有重复字符的最长子串的长度。
提示：
- 0 <= s.length <= 5 * 104
- s 由英文字母、数字、符号和空格组成
解题思路
完整代码
209.长度最小的子数组
给定一个含有n个正整数的数组和一个正整数target。
找出该数组中满足其总和大于等于target的长度最小的子数组 [numsl, numsl+1, …, numsr-1, numsr]，并返回其长度。如果不存在符合条件的子数组，返回0。
提示：
- 1 <= target <= 109
- 1 <= nums.length <= 105
- 1 <= nums[i] <= 104
进阶：
- 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
解题思路
在数组字串问题中，经常会用到双指针这一技巧。
暴力方法 时间复杂度
O(n^2)枚举右端点，收缩左端点 时间复杂度
O(n)
- 拿到数组的长度n
- 答案ans初始化为n+1或者更大
- 总和sum初始化为0
- 左端点left初始化为0
- right右端点for循环(0~n-1)：sum+=nums[right]
- for嵌套while(s-nums[left]):此时子数组的和减去左端点依旧>=target：sum-=nums[left];left+=1;(移掉左端点)
- 如果sum>=target:更新答案最小值 ans=min(ans,right-left+1)
- 返回ans（<=n返回ans，否则返回0）
注意：此题不需要判断left和right两者间的大小关系。
因为当left=right时，s-nums[left]=0，一定比target小（target为正整数），不满足while条件。
- 在「2」的基础上，把ans的更新写到while里面
完整代码
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n,ans,sum,left;
n=nums.size();
ans=n+1;
sum=left=0;
for(int i=0;i<n;i++){
// sum+=nums[i];
// while(sum-nums[left]>=target){
// sum-=nums[left];
// left++;
// }
// if(sum>=target){
// ans=min(ans,i-left+1);
// }
while(sum>=target){
ans=min(ans,i-left+1);
sum-=nums[left++];
}
}
return ans<=n?ans:0;
}
};
2269.找到一个数字的 K 美丽值
今天字符串也要美丽了🆘
一个整数num的k美丽值定义为num中符合以下条件的子字符串数目：
- 子字符串长度为k。
- 子字符串能整除num。
给你整数num和k，请你返回num的k美丽值。
注意：
允许有前缀0。
0不能整除任何值。
一个子字符串是一个字符串里的连续一段字符序列。
提示：
1 <= num <= 1091 <= k <= num.length（将 num 视为字符串）
解题思路
我觉得这道的要点就是子串怎么得，剩下的就好判断了。偏偏我就栽在这儿了😅
- int转string
to_string()注意此函数需要赋给个string变量 - string转int
stoi()同样，需要赋给个int变量 - 获取长度为k的字符串
substr(i,k)距离c++学这个函数已经过了一两年了，忘的一干二净，趁此好机会来总结一下。
👇️ 获取子串
| 函数 | 作用 |
|---|---|
substr(pos,len) |
从pos开始，提取长度为len的子串 |
👇️ 查找字符串
| 函数 | 作用 |
|---|---|
find(str,pos) |
在pos之后查找str的位置，找不到返回string::pos |
rfind(str,pos) |
逆向查找str,从pos开始向前找 |
find_first_of(chars,pos) |
查找chars中的任意字符的第一次出现 |
find_last_of(chars,pos) |
查找chars中的任意字符的最后一次出现 |
👇️ 替换字符串
| 函数 | 作用 |
|---|---|
replace(pos,len,str) |
从pos开始，用str替换len个字符 |
erase(pos,len) |
删除从pos开始的len个字符 |
insert(pos,str) |
在pos位置插入str |
👇️ 大小写转换
| 函数 | 作用 |
|---|---|
toupper(c) |
将字符c转换为大写 |
tolower(c) |
将字符c转换为小写 |
👇️ 数字与字符串转换
| 函数 | 作用 |
|---|---|
to_string(num) |
把num转换为字符串 |
stoi(str) |
把str转换为int |
stol(str) |
把str转换为long |
stod(str) |
把str转换为double |
完整代码
class Solution {
public:
int divisorSubstrings(int num, int k) {
int cnt=0;
string str=to_string(num);
for(int i=0;i<=str.size()-k;i++){
string ans=str.substr(i,k);
int answer=stoi(ans);
if(answer!=0 && num%answer==0){
cnt++;
}
}
return cnt;
}
};
3305.元音辅音字符串计数Ⅰ
给你一个字符串word和一个非负整数 k。
返回word的子字符串中，每个元音字母（’a’、’e’、’i’、’o’、’u’）至少出现一次，并且恰好包含k个辅音字母的子字符串的总数。
提示：
- 5 <= word.length <= 250
- word 仅由小写英文字母组成。
- 0 <= k <= word.length - 5
解题思路
先试了试暴力😤循环套三层观感太差，不放上来。
正经解法
- 滑动窗口代替暴力循环
- 哈希表统计元音出现次数
注意几个用法
1️⃣ 几个键值对容器
| 键值对容器 | 实现方式 | 键值 | 时间复杂度 | 是否有序 | 使用场景 |
|---|---|---|---|---|---|
unordered_map |
哈希表 | 键-值对 | 平均O(1) | 无序 | 快速查找键对应的值 |
map |
红黑树 | 键-值对 | O(logn) | 有序 | 需要有序键值对 |
unordered_set |
哈希表 | 键 | 平均O(1) | 无序 | 快速查找元素是否存在 |
set |
红黑树 | 键 | O(logn) | 有序 | 需要排序的集合 |
2️⃣ 键值对容器+函数求的是什么？
unordered_map.size()返回unordered_map中键值对的数量。unordered_set.count(x)unordered_set中某个元素是否存在，返回1表示在，0表示不在。
代码思路如下。这个方法时间空间上并非最优，后续需要调整思路。
定义n：word长度;
定义unordered_map类型的vowel_cnt:元音出现次数;
定义consonant_cnt:辅音个数;
定义ans：统计最终答案;
定义unordered_set类型的vowels:所有元音字母;
定义左指针j=0;
遍历word从下标0~word.size():
定义右元素right=word[i];
统计元音出现次数：
进行元/辅音计数;
当辅音数量超过k://收缩窗口左边界
定义左元素left=word[左指针];//取左边界字符
如果left是元音：
该元音出现次数--;
当元音的计数减少到0时：
将它从vowel_cnt中删除；
否则：
辅音个数--;
左指针右移;
如果包含所有元音且辅音个数为k:
//避免修改原窗口状态,思路整体与上半部分相同☝️
定义临时变量temp_vowel=vowel_cnt;
定义临时变量temp_consonant=consonant_cnt;
定义临时变量temp_j=j;
定义计数cnt=0;
当临时左下标<=右下标:
如果包含所有临时元音且临时辅音个数为k:
cnt++;
否则:
退出该层循环;
定义c:word[临时左指针];
如果c是元音：
临时该元音出现次数--;
当临时元音的计数减少到0时：
将它从临时vowel_cnt中删除;
否则:
临时辅音个数--;
临时左指针j右移;
ans+=cnt;
返回ans;
完整代码
class Solution {
public:
int countOfSubstrings(string word, int k) {
int len=word.size();
unordered_map<char,int>vowel_cnt;
int consonant_cnt=0;
int ans=0;
unordered_set<int>vowels={'a','e','i','o','u'};
int j=0;
for(int i=0;i<len;i++){
char right=word[i];
if(vowels.count(right)){
vowel_cnt[right]++;
}
else{
consonant_cnt++;
}
while(consonant_cnt>k){
char left=word[j];
if(vowels.count(left)){
vowel_cnt[left]--;
if(vowel_cnt[left]==0){
vowel_cnt.erase(left);
}
}
else{
consonant_cnt--;
}
j++;
}
if(vowel_cnt.size()==5 && consonant_cnt==k){
unordered_map<char,int>temp_vowel=vowel_cnt;
int temp_consonant=consonant_cnt;
int temp_j=j;
int cnt=0;
while(temp_j<=i){
if(temp_vowel.size()==5 && temp_consonant==k){
cnt++;
}
else{
break;
}
int c=word[temp_j];
if(vowels.count(c)){
temp_vowel[c]--;
if(temp_vowel[c]==0){
temp_vowel.erase(c);
}
}
else{
temp_consonant--;
}
temp_j++;
}
ans+=cnt;
}
}
return ans;
}
};
3306.元音辅音字符串计数Ⅱ
不行，彻底懵了脑子转不动做梦都是元辅音😫先把copy的官方题解放这，过两天我再苟回来看。
解题思路
完整代码
class Solution {
public:
long long countOfSubstrings(string word, int k) {
set<char> vowels = {'a', 'e', 'i', 'o', 'u'};
auto count = [&](int m) -> long long {
int n = word.size(), consonants = 0;
long long res = 0;
map<char, int> occur;
for (int i = 0, j = 0; i < n; i++) {
while (j < n && (consonants < m || occur.size() < vowels.size())) {
if (vowels.count(word[j])) {
occur[word[j]]++;
} else {
consonants++;
}
j++;
}
if (consonants >= m && occur.size() == vowels.size()) {
res += n - j + 1;
}
if (vowels.count(word[i])) {
occur[word[i]]--;
if (occur[word[i]] == 0) {
occur.erase(word[i]);
}
} else {
consonants--;
}
}
return res;
};
return count(k) - count(k + 1);
}
};
