6.4-滑动窗口

本文最后更新于 2024年10月21日 早上

26.删除有序数组中的重复项

题意描述：

给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

  • 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
  • 返回 k 。

思路：双指针

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {

public:

  int removeDuplicates(vector<int>& nums) {
    	if(nums.size() == 0)  return 0;  //这里是没考虑到的地方，虽然过了
    
    	int slow = 1;

    	for(int fast = 1 ; fast < nums.size(); fast ++){

     	if(nums[fast - 1] != nums[fast]) nums[slow ++] = nums[fast];

    }

    return slow;

  }

};

283.移动零

题意描述：

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

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

思路：双指针，相当于删除0，然后slow指针的右边全赋0，但用两个循环代价较大。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {

public:

  void moveZeroes(vector<int>& nums) {

   int slow = 0;

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

    if(nums[fast]) nums[slow++] = nums[fast];

   }

   for(;slow < nums.size() ; slow++) nums[slow] = 0;

}

};

官方思路代码：

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

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

注意到以下性质：

左指针左边均为非零数；

右指针左边直到左指针处均为零。

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

1
2
3
4
5
6
7
8
9
class Solution{
public:
        void moveZeroes(vector<int>& nums){
          int l = 0;
          for(int r = 0 ; r < nums.size() ; r++){
            if(nums[r])  swap(nums[l++] , nums[r]);
          }
        }
}

844.比较含退格的字符串

==本题没A出来，以黄色标记==

题意描述：

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

方法一：双指针

一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。

具体地，我们定义 skip表示当前待删除的字符的数量。每次我们遍历到一个字符：

若该字符为退格符，则我们需要多删除一个普通字符，我们让 skip 加 1；

若该字符为普通字符：

若 skip 为 0，则说明当前字符不需要删去；

若 skip 不为 0，则说明当前字符需要删去，我们让 skip减 1。

这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。

AC代码：

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
class Solution {
public:
    bool backspaceCompare(string s, string t) {
     int i = s.length() - 1 , j = t.length() - 1;
     int skips = 0 , skipt = 0;

     while(i >= 0 || j >= 0){
        while(i >= 0){
          if(s[i] == '#') {
            skips++ , i--;
          } 
          else if(skips > 0) {
            skips -- , i --;
          }
          else  break;
        }
        while(j >= 0){
          if(t[j] == '#'){
            skipt++ , j --;
          }
          else if(skipt > 0){
            skipt -- , j --;
          }
          else break;
        }
     if(i >= 0 && j >= 0 )  {
      if(s[i] != t[j])  return false;
     }
     else{
      if(i >= 0 || j >= 0)  return false;
     }
     i -- , j --;
     }
     return true;
    }
};

方法二：重构字符串，栈实现

思路及算法

最容易想到的方法是将给定的字符串中的退格符和应当被删除的字符都去除，还原给定字符串的一般形式。然后直接比较两字符串是否相等即可。

具体地，我们用栈处理遍历过程，每次我们遍历到一个字符：

如果它是退格符，那么我们将栈顶弹出；

如果它是普通字符，那么我们将其压入栈中。

复杂度分析

时间复杂度：O(N+M)，其中 N 和 M分别为字符串 S 和 T 的长度。我们需要遍历两字符串各一次。

空间复杂度：O(N+M))，其中 N和 M分别为字符串 S 和 T的长度。主要为还原出的字符串的开销。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool backspaceCompare(string s, string t) {
      return build(s) == build(t);
    }

    string build(string str){
      string ret;
      for(char ch: str){
        if(ch != '#')  ret.push_back(ch);
        else if(!ret.empty())  ret.pop_back();
      }
      return ret;
    }
};

977.有序数组的平方

题意描述：

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

进阶：

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

思路与算法

数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

如果A[i] * A[i] < A[j] * A[j] 那么result[k--] = A[j] * A[j]; 。

如果A[i] * A[i] >= A[j] * A[j] 那么result[k--] = A[i] * A[i]; 。

选择较大的那个逆序放入答案并移动指针。这种方法无需处理某一指针移动至边界的情况。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n);
        for(int i = 0 , j = n - 1 , pos = n - 1 ; i <= j;){
          if(nums[i] * nums[i] > nums[j] * nums[j]){
            ans[pos] = nums[i] * nums[i];
            i++;          
          }
          else {
            ans[pos] = nums[j] * nums[j];
            j--;
          }
          pos --;
        }
        return ans;
    }
};

法二：

思路与算法

方法一没有利用「数组 nums已经按照升序排序」这个条件。显然，如果数组 nums中的所有数都是非负数，那么将每个数平方后，数组仍然保持升序；如果数组 nums中的所有数都是负数，那么将每个数平方后，数组会保持降序。

这样一来，如果我们能够找到数组 nums中负数与非负数的分界线，那么就可以用类似「归并排序」的方法了。具体地，我们设 neg为数组 nums中负数与非负数的分界线，也就是说，nums[0]到nums[neg] 均为负数，而nums[neg+1] 到 nums[n−1] 均为非负数。当我们将数组 nums中的数平方后，那么nums[0]到nums[neg] 单调递减，nums[neg+1] 到 nums[n−1] 单调递增。

由于我们得到了两个已经有序的子数组，因此就可以使用归并的方法进行排序了。具体地，使用两个指针分别指向位置neg和 neg+1，每次比较两个指针对应的数，选择较小的那个放入答案并移动指针。当某一指针移至边界时，将另一指针还未遍历到的数依次放入答案。

AC代码：

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
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int n = nums.size();
        //找分界点negative
        int negative = -1;
        for(int i = 0 ; i < n ; i ++){
          if(nums[i] < 0) negative = i;
          else  break;
        }

        vector<int> ans;
        int i = negative , j = negative + 1;
        while(i >= 0 || j < n){
          //负数那组已经排完
          if(i < 0){
            ans.push_back(nums[j] * nums[j]);
            j++;
          }
          //正数已经排完
          else if(j == n){
            ans.push_back(nums[i] * nums[i]);
            i--;
          }
          //小的计入ans，按从小到大顺序排
          else if (nums[i] * nums[i] < nums[j] * nums[j]){
            ans.push_back(nums[i] * nums[i]);
            i--;
          }
          else{
            ans.push_back(nums[j] * nums[j]);
            j++;
          }
        }
        return ans;
    }
};

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

空间复杂度：O(1)。除了存储答案的数组以外，我们只需要维护常量空间。

209.长度最小的子数组

题意描述：

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

  • 输入：s = 7, nums = [2,3,1,2,4,3]
  • 输出：2
  • 解释：子数组 [4,3] 是该条件下的长度最小的子数组。

提示：

  • 1 <= target <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^5

思路：滑动窗口

所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。

在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。

首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置。

如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？此时难免再次陷入 暴力解法的怪圈。

所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。

关键点在于==滑动窗口的起始位置如何移动==呢？

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int result = INT32_MAX;//赋0x3f3f3f3f也可
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
            while (sum >= target) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）
            }
        }
        // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

M：904.水果成篮(opens new window)

题意描述：

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

  • 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
  • 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
  • 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

1
2
3
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

1
2
3
4
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

1
2
3
4
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

1
2
3
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

提示：

  • 1 <= fruits.length <= 105
  • 0 <= fruits[i] < fruits.length

思路：

可以使用滑动窗口解决本题，left和 right 分别表示满足要求的窗口的左右边界，同时我们使用哈希表存储这个窗口内的数以及出现的次数。

我们每次将 right 移动一个位置，并将 fruits[right] 加入哈希表。如果此时哈希表不满足要求（即哈希表中出现超过两个键值对），那么我们需要不断移动 left，并将 fruits[left]从哈希表中移除，直到哈希表满足要求为止。

需要注意的是，将 fruits[left] 从哈希表中移除后，如果 fruits[left] 在哈希表中的出现次数减少为 0，需要将对应的键值对从哈希表中移除。

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
      int n = fruits.size();
      unordered_map<int , int> cnt;

      int l = 0 , ans = 0;
      for(int r = 0; r < n; r++){
        cnt[fruits[r]]++;
        while(cnt.size() > 2){
          auto it = cnt.find(fruits[l]);
          --it ->second;
          if(it->second == 0) cnt.erase(it);
          l++;
        }
        ans = max(ans , r - l + 1);
      }
      return ans;
    }    
};

H:76.最小覆盖子串(opens new window)

题意描述：

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

注意：

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

示例 1：

1
2
3
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

1
2
3
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。

示例 3:

1
2
3
4
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

提示：

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

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

思路：

本问题要求我们返回字符串 s 中包含字符串 t 的全部字符的最小窗口。我们称包含 t 的全部字母的窗口为「可行」窗口。

我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在s 上滑动窗口，通过移动 r指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

如何判断当前的窗口包含所有 t 所需的字符呢？我们可以用一个哈希表表示 t 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 t 的哈希表中的所有字符，并且对应的个数都不小于 t 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。

注意：这里 t 中可能出现重复的字符，所以我们要记录字符的个数。

fig1

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
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
public:
    //定义两个哈希表，tstr用来存放t中元素的出现次数信息，sstr用来存放滑动窗口中元素的出现次数信息
    unordered_map<char,int> tstr,sstr;

    //检查当前的窗口是否是合格的窗口，即：
    //检查当前滑动窗口中元素是否完全覆盖了字符串t中的所有元素（重点是某元素的出现次数必须不小于t中对应元素的出现次数）
    bool check()
    {
        for(auto tchar : tstr)
            {
                if(tchar.second > sstr[tchar.first]) return false;//注意这里的判断条件是大于
                //只要sstr中元素的second值不小于tchar中对应元素的second值就行
            }
        return true;
    }

    string minWindow(string s, string t) {
        int n1 = s.size(),n2 = t.size();
        if(n1<n2) return "";//如果t串比s串还长，s中肯定不能找到相应的子串
        int len = INT_MAX;//最小窗口的长度
        int ans_left = -1;//最小窗口的左边界指针
        //构造哈希表
        for(auto tchar : t)
            ++tstr[tchar];
        
        int left = 0,right = 0;//窗口的左右两端指针
        //滑动窗口右端指针遍历整个s串
        for(int right = 0;right<n1;right++)
        {   
            //每遍历一个元素，更新sstr中的元素信息
            ++sstr[s[right]];
            //如果当前遍历到的元素在tstr中也有，说明此次遍历的更新是有效的更新，否则不用管，直接继续遍历
            if(tstr.find(s[right]) != tstr.end())
            { 
                //对于每一次有效的更新，检查当前窗口中的子串是否是一个合格的子串
                while(check() && left<=right)
                {
                    //如果当前子串是合格的，那么判断是否是最小的窗口
                    if(len > right - left +1)
                    {
                        //如果是最小的窗口，那么更新窗口信息
                        ans_left = left;
                        len = right - left + 1;
                    }

                    //当前子串如果是合格的，那么尝试移进窗口的左边界缩短窗口的长度
                    --sstr[s[left]];//窗口左边界的元素信息从哈希表sstr中删除
                    left++;//移进窗口左边界

                    //移进之后，继续while判断移进后的子串是否是合格的，如果是合格的，继续重复同样的操作，更新窗口的信息
                }

                //一旦窗口不合格，窗口右边界的指针就继续往后遍历，拓宽窗口的长度
            }
        }
        if(ans_left == -1) return "";
        else return s.substr(ans_left,len);
    }
};
代码随想录
#LEECODE
6.4-滑动窗口
https://bing.7dragonpig.cn/posts/1375ccb7/
作者
七龙猪
发布于
2024年6月4日
许可协议