【力扣刷题】双指针和滑动窗口
本文总结了双指针和滑动窗口的常见题型。
双指针
双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作，达到减少时间复杂度的作用。
双指针法在数组和链表的操作中是非常常见的，很多考察数组、链表、字符串等操作的面试题，都使用双指针法。
27. 移除元素
27. 移除元素：给你一个数组
nums和一个值val，你需要 原地 移除所有数值等于val的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用
O(1)额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 ：
输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
数组的基础知识可以看这里程序员算法面试中，必须掌握的数组理论知识。
本题思路是，设置快慢指针，先同时移动，直到指向第一个要删除的位置，快指针多移动一位。
之后每次同时移动，做两件事：
- 快指针位置的值复制到慢指针位置
- 快指针指向要删除位置时，快指针多移动一位
最后慢指针位置即为数组长度。
// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
if (val != nums[fastIndex]) {
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};
时间复杂度：
空间复杂度：
26. 删除有序数组中的重复项
26. 删除有序数组中的重复项：给你一个有序数组
nums，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 ：
输入：nums = [1,1,2] 输出：2, nums = [1,2] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
注意到数组有序，因此重复元素必定相邻，那就简单多了。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
// 判空
if (nums.size()==0) return 0;
// 如果非空，第一个数字不变，从第二个开始
int l = 1;
for (int r = 1; r < nums.size(); r++){
if (nums[r] != nums[l-1]){
nums[l++] = nums[r];
}
}
return l;
}
};
时间复杂度：，其中 n 是数组的长度。快指针和慢指针最多各移动 n 次。
空间复杂度：，只需要使用常数的额外空间。
80. 删除有序数组中的重复项 II
80. 删除有序数组中的重复项 II：给你一个有序数组
nums，请你** 原地** 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 ：
输入：nums = [1,1,1,2,2,3] 输出：5, nums = [1,1,2,2,3] 解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
本题要求最多出现2次，直接的思路是加个计数项，如果重复个数超过2个就加一次拷贝动作。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size()==0) return 0;
int l = 1, r = 1, cnt = 0;//计数
while (r < nums.size()){
if (nums[r] != nums[r-1]){
//加一次拷贝动作
if (cnt > 0) {
nums[l++] = nums[r-1];
cnt = 0;
}
nums[l++] = nums[r];
}else{
cnt++;
}
r++;
}
// 结尾还要加一次拷贝动作
if (cnt > 0) {
nums[l++] = nums[r-1];
cnt = 0;
}
return l;
}
};
扩展一下，如果要求最多重复k次呢？
class Solution {
public:
int removeDuplicates(vector<int>& nums, int k) {
if (nums.size() <= k) return nums.size();
int l = k, r = k;
while (r < nums.size()){
if (nums[r] != nums[l-k]){
nums[l++] = nums[r];
}
r++;
}
return l;
}
};
时间复杂度：，其中 n 是数组的长度。我们最多遍历该数组一次。
空间复杂度：，我们只需要常数的空间存储若干变量。
844. 比较含退格的字符串
844. 比较含退格的字符串：给定
s和t两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。#代表退格字符。如果相等，返回
true；否则，返回false。**注意：**如果对空文本输入退格字符，文本继续为空。
示例 ：
输入：s = "ab#c", t = "ad#c" 输出：true 解释：S 和 T 都会变成 “ac”。
本题中一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
具体地，我们定义cnts、cntt表示当前待删除的字符的数量。每次我们遍历到一个字符：
若该字符为退格符，则我们需要多删除一个普通字符，我们让cnts、cntt加 1；
若该字符为普通字符：
若cnts、cntt为 0，则说明当前字符不需要删去；
若cnts、cntt不为 0，则说明当前字符需要删去，我们让cnts、cntt减 1。
这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。
class Solution {
public:
bool backspaceCompare(string s, string t) {
int ps = s.length() - 1, pt = t.length() - 1;
int cnts = 0, cntt = 0;
while (ps >= 0 || pt >= 0){
// s中查找下一个需要比较的字符
while (ps >= 0){
if (s[ps] == '#'){
cnts++; ps--;
}
else if (cnts > 0){
cnts--; ps--;
}
else{
break;
}
}
// t中查找下一个需要比较的字符
while (pt >= 0){
if (t[pt] == '#'){
cntt++; pt--;
}
else if (cntt > 0){
cntt--; pt--;
}
else{
break;
}
}
// ps、pt同时为0才可能相等
if (ps >= 0 && pt >= 0){
if (s[ps] != t[pt]){
return false;
}
}// 不同时为0直接结束比较
else{
if (ps >= 0 || pt >= 0){
return false;
}
}
ps--; pt--;
}
return true;
}
};
时间复杂度：，其中 N 和 M 分别为字符串 S 和 T 的长度。我们需要遍历两字符串各一次。
空间复杂度：。对于每个字符串，我们只需要定义一个指针和一个计数器即可。
977.有序数组的平方
977. 有序数组的平方：给你一个按 非递减顺序 排序的整数数组
nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。示例 ：
输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100] 排序后，数组变为 [0,1,9,16,100]
数组其实是有序的， 只不过负数平方之后可能成为最大数了。
那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法了，i指向起始位置，j指向终止位置。
定义一个新数组result，和nums数组一样的大小，让k指向result数组终止位置。
如果nums[i] * nums[i] < nums[j] * nums[j] 那么result[k--] = nums[j] * nums[j]; 。
如果nums[i] * nums[i] >= nums[j] * nums[j] 那么result[k--] = nums[i] * nums[i]; 。
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
int l = 0, r = n - 1, k = n - 1;
vector<int> res(n);
while (k>=0){
if (nums[l] * nums[l] > nums[r] * nums[r]){
res[k--] = nums[l] * nums[l];
l++;
}
else{
res[k--] = nums[r] * nums[r];
r--;
}
}
return res;
}
};
时间复杂度：，其中 n 是数组 nums 的长度，相对于暴力排序的解法还是提升不少的。
空间复杂度：。除了存储答案的数组以外，我们只需要维护常量空间。
滑动窗口
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
滑动窗口也可以理解为双指针法的一种，只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。
实现滑动窗口，主要确定如下三点：
- 窗口内是什么？（题目要求）
- 如何移动窗口的起始位置？（判断条件）
- 如何移动窗口的结束位置？（遍历指针）
209.长度最小的子数组
209.长度最小的子数组：给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
本题中的窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。
窗口的起始位置如何移动：如果当前窗口的值大于s了，窗口就要向前移动了（也就是该缩小了）。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。
由于结束位置直接跟着循环跑，不用自己移动，所以滑动窗口也可以看作单指针。
可以发现滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将O(n^2)的暴力解法降为O(n)。
C++代码如下：
class Solution {
public:
int minSubArrayLen(int s, vector<int>& nums) {
int result = INT32_MAX;
int sum = 0; // 滑动窗口数值之和
int i = 0; // 滑动窗口起始位置
int subLength = 0; // 滑动窗口的长度
for (int j = 0; j < nums.size(); j++) {
sum += nums[j];
// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
while (sum >= s) {
subLength = (j - i + 1); // 取子序列的长度
result = result < subLength ? result : subLength;
sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
}
}
// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
return result == INT32_MAX ? 0 : result;
}
};
时间复杂度：
空间复杂度：
为什么时间复杂度是O(n)。
不要以为for里放一个while就以为是， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被被操作两次，所以时间复杂度是2 * n 也就是。
904.水果成篮
904. 水果成篮：在一排树中，第
i棵树产生tree[i]型的水果。你可以从你选择的任何树开始，然后重复执行以下步骤：
- 把这棵树上的水果放进你的篮子里。如果你做不到，就停下来。
- 移动到当前树右侧的下一棵树。如果右边没有树，就停下来。
请注意，在选择一颗树后，你没有任何选择：你必须执行步骤 1，然后执行步骤 2，然后返回步骤 1，然后执行步骤 2，依此类推，直至停止。
你有两个篮子，每个篮子可以携带任何数量的水果，但你希望每个篮子只携带一种类型的水果。
用这个程序你能收集的水果树的最大总量是多少？
示例 ：
输入：[0,1,2,2] 输出：3 解释：我们可以收集 [1,2,2] 如果我们从第一棵树开始，我们将只能收集到 [0, 1]。
本题需要记录不同类型水果个数，使用哈希表当篮子。
本题中的窗口就是 两个装有不同类型水果的篮子。
窗口的起始位置如何移动：如果当前篮子数目大于2了，窗口就要向前移动了，同时依次减持水果，直到篮子数目重回2。
窗口的结束位置如何移动：窗口的结束位置就是遍历数组的指针，窗口的起始位置设置为数组的起始位置就可以了。
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> basket;
int result = 0, len = 0;
int left = 0;
for (int i = 0; i < fruits.size(); i++) {
basket[fruits[i]]++;
len++;
while (basket.size() > 2) {
basket[fruits[left]]--; //减掉left是因为采果子必须按顺序连续采
if (basket[fruits[left]] == 0) basket.erase(fruits[left]); //直到某一个篮子为空
left++;
len--;
}
// 结束位置每移动一次，维护一次最大值
result = max(result,len);
}
return result;
}
};
时间复杂度：
空间复杂度：
76.最小覆盖子串
76. 最小覆盖子串： 给你一个字符串
s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。- 如果
s中存在这样的子串，我们保证它是唯一的答案。示例 ：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC"
本题由于t中存在重复字符，需要通过计数，确定字符是否找齐。
用j,i表示滑动窗口的左边界和右边界，当这个窗口包含的元素满足条件，即包含字符串t的所有元素，记录下这个滑动窗口的长度i-j+1，这些长度中的最小值就是要求的结果。
步骤一
不断增加i使滑动窗口增大，直到窗口包含了t的所有元素（通过计数判断）
步骤二
不断增加j使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，记录此时滑动窗口的长度，并保存最小值
步骤三
让j再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤一开始执行，寻找新的满足条件的滑动窗口，如此反复，直到i超出了字符串s范围。
class Solution {
public:
string minWindow(string s, string t) {
int n = s.size(), m = t.size();
vector<int> hash(128);
for (char c : t) hash[c]--;
string res = "";
for (int i = 0, j = 0, cnt = 0; i < n; i++) {
hash[s[i]]++;
// 计数，t中的字符有几个被找到
if (hash[s[i]] <= 0) cnt++;
// 找齐之后，要缩减一次长度，移动起始位置
while (cnt == m && hash[s[j]] > 0) hash[s[j++]]--;
// 缩减之后，比较并存最短长度
if (cnt == m){
if (res == "" || res.size() > i - j + 1){
res = "";
// 取[j,i]的子字符串
for (int k = j; k <= i; k++){
res += s[k];
}
}
}
}
return res;
}
};
时间复杂度：
空间复杂度：