【Leetcode每日一刷】数组|双指针篇：977. 有序数组的平方、76. 最小覆盖子串（附滑动窗口法详解）

本文主要是介绍【Leetcode每日一刷】数组|双指针篇：977. 有序数组的平方、76. 最小覆盖子串（附滑动窗口法详解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、977. 有序数组的平方

1.1题目

[题目链接](

1.2、解题思路

• 题型：双指针——左右指针

• 关键：当有可能含负数的有序数组平方后，最大值只有可能位于数组两侧，整个数组呈一个凹函数，从两边向中间递减。

• 思路：如果把这题只是当作普通的排序题做，其实就没有意义了。大不了就是调用库函数sort(nums.begin(), nums.end())进行排序；
  但是这题的关键如上，也就是平方后数组由两边向中间递减，最大值只有可能位于两侧。由于这样的特性，利用双指针， 从两边向中间探测，互相比较，逐渐挑出最大值，再到次最大值…一直到最小值。
  1). 设置左右两个指针left和right,位于数组两侧
  2).设置新数组，大小和元素中相同。
  3).循环条件为while(left <= right)，每次循环，将左指针和右指针处的元素进行比较。谁大，就把元素放入新数组（从尾端开始放起）。

1.3、代码实现——C++

1. 暴力解法

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {for(int i =0; i < nums.size(); i++){nums[i] = nums[i]*nums[i];}sort(nums.begin(), nums.end());//快速排序O(nlogn)return nums;}
};

2. 双指针解法(时间复杂度O(n))

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {for(int i =0; i < nums.size(); i++){nums[i] = nums[i]*nums[i];}vector<int> res(nums.size());int left = 0;int right = nums.size()-1;int i = nums.size()-1;while(left <= right){if(nums[right] >= nums[left]){res[i--] = nums[right];right--;}else{res[i--] = nums[left];left++;}}return res;}
};

二、76. 最小覆盖子串

2.1：题目

题目链接🔗

2.2、解题思路

• 题型：滑动窗口；时间复杂度：O(n)
  🪧 滑动窗口本质也是双指针的一种技巧，特别适用于字串问题

• ❗❗核心思想/ 关键：左右指针滑窗口，一前一后齐头进。

  1. 首先初始化left = 0和right = 0两个左右指针，表示左闭右开区间(0, 0](表示初始时窗口中没有元素）

  初始化两边都闭[0, 0]，那么初始化窗口就包含一个元素；初始化两边都开(0,0),那么让right向后移动一位，开区间任然没有元素(0, 1]。只有初始化为左闭右开区间(0, 0]最方便：right向右移动一位：添加一个元素进窗口；left向左移动一位，剔除窗口左边元素。

  2. 不断增加right指针，增加窗口[left, right)中的元素，直到：窗口[left, right)中的元素都符合要求。———— 寻找可行解⭐

  3. 此时，停止增加right指针，转而不断减小left指针，直到窗口[left, right)的元素都不符合要求；此时，再继续增加right指针。🔺注意：每次增加left指针来缩小窗口[left, right)时，都要更新一轮结果！———— 优化可行解⭐

  4. 不断重复2）和3）步，直到right指针走到数组/ 字符串的尽头。———— 得到最终的最优解

• 算法框架：注意下面框架中的6个关键点！

  /* 滑动窗口算法框架 */
  void slidingWindow(string s) {// ⭐1)用合适的数据结构记录窗口中的数据情况（以便和所需的可行解进行比对）unordered_map<char, int> window;// ⭐2)// 记录最小符合条件子串的起始索引及长度int start = 0, len = INT_MAX; //根据实际算法所需答案进行调整int left = 0, right = 0;while (right < s.size()) {// c 是将移入窗口的字符char c = s[right];window.add(c)// 增大窗口right++;// ⭐3）进行增大窗口后，更新关于记录当前窗口内数据情况的变量（以便稍后和所需的可行解进行比对）.../*** debug 输出的位置 ***/// 注意在最终的解法代码中不要 print// 因为 IO 操作很耗时，可能导致超时printf("window: [%d, %d)\n", left, right);/********************/// ⭐4）找到可行解——判断左侧窗口是否要收缩（进行更新）while (left < right && window needs shrink) {//进入到这个while里面说明找到一个可行解//⭐5）进行最终的所需的答案更新// eg:在这里更新符合条件的*最小*子串（即最终结果）if (right - left < len) {start = left;len = right - left;}// d 是将移出窗口的字符char d = s[left];window.remove(d)// 缩小窗口left++;// ⭐6）进行缩小窗口后，更新关于记录当前窗口内数据情况的变量（以便稍后和所需的可行解进行比对）...}}
  }

  🌟1. 3)和6)的操作分别是扩大和缩小窗口后的更新操作，等会你会发现它们操作是完全对称的。作用都是更新当前窗口中的数据情况，再拿去和题目所需的可行解进行比对，判断当前窗口内的情况是否可行！

  🌟2. 5)步也很关键，它的作用是：找到一个可行解&更新得到一个可行解后，对题目最终需要的最优答案进行更新！

• 本题思路：

  1. 首先，初始化两张哈希表unordered_map: window和need，分别表示：当前[left, right)窗口中的字符情况和所需情况。——两者的情况进行比对，判断当前窗口中的情况是否可行。
  2. 初始化left和right指针，进行窗口滑动.
  3. 设置和初始化答案变量start和len，进行最终最优答案的实时更新和记录。
  4. 关于本题的特殊地方：设置一个辅助变量valid，作用是判断当前window中有效字符个数（只有当window中的这个字符在need中，且这个字符的个数和need中这个字符对应的个数相等,valid才会+1。

     这个相当于一个小细节，只有window和need，把两个进行比对，当然也OK。但是这题的可行情况并不是当window和need完全一样时，就可行，换句话说，就是不能直接把window和need进行对比。因为最优window很有可能覆盖了need，但是还有其他字符。所以valid的作用：记录当前窗口的可行性情况，与need进行比对！

2.3：代码实现——c++

class Solution {
public:string minWindow(string s, string t) {unordered_map<char, int> window, need;//初始化window和need数组for (char c : t){need[c] ++;window[c] = 0;}int valid = 0;//记录当前window中的有效字符个数（方便后续判断当前window是否可行）int start = 0; int len = INT_MAX;// 存储答案的变量，需要在window符合情况时，进行实时更新int left = 0; int right = 0; // 双指针，控制window滑动窗口的大小while(left <= right && right < s.size()){//c是right++后待移入窗口中的元素char c = s[right];// right++ 扩大滑动窗口right ++;//扩大窗口后更新记录窗口情况的window和valid的大小（方便后续判断当前window是否可行if(need.count(c)){// 当前元素c包含在need中window[c]++;if(window[c] == need[c]){valid++;}}//判断当前window中情况是否可行while( valid == need.size() ){//首先，获得一个or更新得到一个可行情况，立即对答案进行更新if(right - left < len){start = left;len = right - left;}// c是left++缩小窗口后待移除的元素char c = s[left];//符合情况，缩小窗口left++;//缩小窗口后更新记录窗口情况的window和valid的大小（方便后续判断当前window是否可行if(need.count(c)){if(window[c] == need[c]){valid--;}window[c]--;}}}// 返回最小覆盖子串return len == INT_MAX ?"" : s.substr(start, len);}
};

2.4：易错点

在实际写代码进行实现时，我犯了两个错误

1. 在对right++和left++来分别扩大和缩小滑动窗口之后，才获得待增加or待移除元素。

   • ❌错误代码

    while(left <= right && right < s.size()){      // right++ 扩大滑动窗口right ++; // ❌此时right从 0 到 1char c = s[right]; //❌c 一开始就获得的不是第一个元素，而是第二个元素//扩大窗口后更新记录窗口情况的window和valid的大小（方便后续判断当前window是否可行if(need.count(c)){// 当前元素c包含在need中window[c]++;if(window[c] == need[c]){valid++;}}

   • ✅ 正确做法：在right++和left++之前，先用变量存储待增加or待减少元素。

     while(left <= right && right < s.size()){//c是right++后待移入窗口中的元素char c = s[right];// right++ 扩大滑动窗口right ++;//扩大窗口后更新记录窗口情况的window和valid的大小（方便后续判断当前window是否可行if(need.count(c)){// 当前元素c包含在need中window[c]++;if(window[c] == need[c]){valid++;}}
   

2. 在缩小窗口部分发生一个逻辑错误：在将元素移除之后，才判断当前valid是否应该减少。

   • ❌错误代码

   		left++;//缩小窗口后更新记录窗口情况的window和valid的大小（方便后续判断当前window是否可行if(need.count(c)){// 当前元素c包含在need中window[c]--;if(window[c] == need[c]){valid--;}}
   

   • ✅ 正确做法：判断valid是否应该减少，应该是基于该元素没有移除之前的情况！

   if(need.count(c)){if(window[c] == need[c]){valid--;}window[c]--;
   }
   

这篇关于【Leetcode每日一刷】数组|双指针篇：977. 有序数组的平方、76. 最小覆盖子串（附滑动窗口法详解）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---