双指针的使用
一、滑动窗口与字符串问题
基本框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void slidingwindow(string s, string t){
unordered_map<char, int> need, window;
for(char c: t) need[c]++;
int l = 0, r = 0, valid = 0;
while(r < s.size()){
char c = s[r];
r++;
while(){
char d = s[l];
l++;
}
}
}
|
题目表例
个人觉得在基本框架之下思路是完整的，判断左侧收缩条件与数据更新是需要深度思考的问题。
76. 最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
1
2
| 输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
|
说明：
- 如果 S 中不存这样的子串，则返回空字符串
""。
- 如果 S 中存在这样的子串，我们保证它是唯一的答案。
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
| #include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
string minwindow(string s, string t){
unordered_map<char, int> need, window;
for(char c: t) need[c]++;
int l = 0, r = 0, valid = 0, start = 0, len = INT_MAX;
while(r < s.size()){
char c = s[r];
r++;
if(need.count(c)){
window[c]++;
if(window[c] == need[c]) valid++;
}
while(valid == need.size()){
if(r - l < len){
start = l;
len = r - l;
}
char d = s[l];
l++;
if(need.count(d)){
if(window[d] == need[d]) valid--;
window[d]--;
}
}
}
if(len == INT_MAX) return "";
else return s.substr(start, len);
}
int main(){
string s, t;
cin >> s;
cin >> t;
cout << minwindow(s, t) << endl;
return 0;
}
|
438. 找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
说明：
- 字母异位词指字母相同，但排列不同的字符串。
- 不考虑答案输出的顺序。
示例 1:
1
2
3
4
5
6
7
8
9
| 输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
|
示例 2:
1
2
3
4
5
6
7
8
9
10
| 输入:
s: "abab" p: "ab"
输出:
[0, 1, 2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。
|
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
| #include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;
vector<int> findAnagrams(string s, string t){
vector<int> ans;
unordered_map<char, int> need, window;
for(char c: t) need[c]++;
int l = 0, r = 0, valid = 0;
while(r < s.size()){
char c = s[r];
r++;
if(need.count(c)){
window[c]++;
if(window[c] == need[c]) valid++;
}
while(r - l >= t.size()){
if(valid == need.size()) ans.push_back(l);
char d = s[l];
l++;
if(need.count(d)){
if(window[d] == need[d]) valid--;
window[d]--;
}
}
}
return ans;
}
int main(){
string s, t;
cin >> s;
cin >> t;
vector<int> ans = findAnagrams(s, t);
for (int i = 0; i < ans.size(); ++i){
cout << ans[i] << " " << endl;
}
return 0;
}
|
567. 字符串的排列
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
换句话说，第一个字符串的排列之一是第二个字符串的子串。
示例1:
1
2
3
| 输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
|
示例2:
1
2
| 输入: s1= "ab" s2 = "eidboaoo"
输出: False
|
注意：
- 输入的字符串只包含小写字母
- 两个字符串的长度都在 [1, 10,000] 之间
二、快慢指针
三、左右指针
This is copyright.