双指针滑动窗口法解析及LeetCode相关题解

“深入分析双指针滑动窗口法，详细LeetCode例题应用”

01

—

经典题目引入

给定一个有限数字序列，长度为n，求连续k个（k<n）数字和的最大值。 https://blog.csdn.net/sinat_21107433/article/details/100170044

看完这个题目，最简单粗暴的方法肯定是用两层for循环：

int maxSum(int arr[], int n, int k){
  int curSum = 0;
  int maxSum = 0;
  for(int i = 0; i <= n - k; i++){
    for (int j = i; j < i + k; j++){
      curSum += arr[j];
    }
    if (curSum > maxSum){
      maxSum = curSum;
    }
    curSum = 0;
  }
  return maxSum;
}

复制

但是显然时间复杂度很高，这里可以采用滑动窗口法来解决这个问题，甚至这一类问题。

02

—

滑动窗口法示例

如下图，n=8,k=3，即求连续3个数和的最大值。可以想象有一个红色的容量为3个数字的矩形窗口在沿着数字序列滑动，有两个指针right和left分别指向窗口的两端：left指向窗口左端，right指向窗口右端。窗口不断滑动的过程其实就是left++，right++的过程，直至right移至数列末端。

代码示例如下：

int maxSum(int arr[], int n, int k){
  int curSum = 0;
  int maxSum = 0;
  int left = 0;
  int right = k - 1;
  for (int i = left; i < k; i++){
    curSum += arr[i];
  }
  maxSum = curSum;
  while (right < n){
    right++;
    curSum = curSum + arr[right] - arr[left];
    left++;
    if (curSum>maxSum){
      maxSum = curSum;
    }
  }
  return maxSum;
}

复制

03

—

LeetCode相关题解

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。示例: 输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。 https://blog.csdn.net/sinat_21107433/article/details/100170044

分析：该题目应用滑动窗口法，需要设置两个指针left和right，把索引闭区间 [left, right] 称为一个「窗口」，其中right指示滑动窗口的右侧，left指示左侧（最后一个元素）；curSum记录当前窗口元素的和。接下来分两种情况：

• 如果curSum小于s，则right右移（right++），继续计算窗口元素的和；
• 如果curSum不小于s，则curLen保存当前窗口的长度，并且与minLen比较；left右移（left++）；

重复上述步骤直至right移至末尾。代码如下：

int minLength(vector<int>arr, int s)
{
  int left = 0;
  int right = 0;
  int curSum = 0;
  int minLen = arr.size()+1;
  int curLen = 0;
  while (right < arr.size()){
    if (curSum + arr[right] < s){
      curSum += arr[right];
      right++;
    }
    else{
      curLen = right - left + 1;
      curSum = curSum - arr[left];
      left++;
      if (curLen < minLen){
        minLen = curLen;
      }
    }
  }
  return curLen == 0 ? 0 : minLen;
}

复制

438. 找到字符串中所有字母异位词

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。 说明：字母异位词指字母相同，但排列不同的字符串。 不考虑答案输出的顺序。 输入: s: "cbaebabacd" p: "abc" 输出: [0, 6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。

分析：同样使用双指针滑动窗口法，本题另一点是判断当前窗口的字母是否是p的异位词的子串，本题采用的方法是用一个长度为26的数组n_p统计p中每个字母出现的次数，然后将当前窗口内的各个字母出现的次数n_s与n_p比较，如果相同，则将left压栈。

vector<int> findAnagrams(string s, string p) {
  if (s.length()<p.length())
    return{};
 
  vector<int>n_s(26, 0);
  vector<int>n_p(26, 0);
  vector<int>res;
 
  int left = 0;
  int right = 0;
  for (right = 0; right<p.length(); right++){
    n_p[p[right] - 'a']++;
    n_s[s[right] - 'a']++;
  }
  if (n_p == n_s){
    res.push_back(left);
  }
 
  while (right  < s.length()){
    
    n_s[s[right] - 'a']++;
    n_s[s[left] - 'a']--;
    right++;
    left++;
    if (n_s == n_p){
      res.push_back(left);
    }
    
  }
  return res;
}

复制

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1: 输入: "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。 示例 2: 输入: "bbbbb" 输出: 1 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。 示例 3: 输入: "pwwkew" 输出: 3 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。

分析：同样使用双指针滑动窗口法,本题判断是否有重复出现的字母的方法与上一题类似，定义一个长度为256的数组window_arr并全部初始化为0；遍历当前窗口子串，将出现的字母对应的数组位置置为1，移动窗口，如果window_arr[right]==1，说明该字符在之前窗口已经出现过，left++；否则right++，并且长度+1。代码如下：

int lengthOfLongestSubstring(string s) {
        int length = s.length();
      if (length == 0)
        return 0;
        
        int curLength = 0;
        int maxLength = 1;
        int left = 0;
        int right = 0;
        int window_arr[256] = {0};
        
        window_arr[s[right]]++;
        right++;
        
        while(right < s.length()){
            if(window_arr[s[right]]==0){
                window_arr[s[right]]++;
                right++;
                curLength = right-left;
                if(curLength>maxLength){
                    maxLength = curLength;
                }
            }
            else{
                window_arr[s[left]]--;
                left++;
            }
        }
 
        return maxLength;
    }

复制

239. 滑动窗口最大值

给定数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。返回滑动窗口中的最大值。

示例:

输入: nums = [1,3,-1,-3,5,3,6,7], k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口位置 最大值 [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7

分析：题目点名是滑动窗口，但此题考察点不仅仅是滑动窗口，还要找寻当前滑动窗口里的最大值。找k个数的最大值很简单，哪怕用遍历方法。但是在滑动窗口中需要分两种情况：

• 上一个滑动窗口的最大值在窗口最左边，这时需要重新遍历下一个窗口，找下一个窗口的最大值；
• 上一个滑动窗口的最大值不在窗口最左边，这时仅需要将下一个窗口的最右边的值与上一个窗口的最大值比较，进而更新最大值。

代码如下：

int findMax(vector<int>&nums, int left, int right){
  int max = nums[left];
  for (int i = left + 1; i <= right; i++){
    if (nums[i] > max){
      max = nums[i];
    }
  }
  return max;
}
 
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  vector<int>res;
  if (k > nums.size() || nums.size() == 0){
    return res;
  }
  int left = 0;
  int right = k - 1;
  int curMax = 0;
  int subMax = 0;
  int i = left;
  curMax = findMax(nums, left, right);
  res.push_back(curMax);
  while (right < nums.size()-1){
    right++;
    left++;
    
    if (curMax == nums[left-1]){// 上一个窗口的最大值curMax在窗口的最左边
      subMax = findMax(nums, left, right);
    }
    else{                       // 上一个窗口的最大值curMax不在窗口的最左边
      subMax = curMax;
    }
    curMax = subMax>nums[right] ? subMax : nums[right];
    res.push_back(curMax);
  }
  return res;
}

复制

76. 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。 示例： 输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC" 说明： 如果 S 中不存这样的子串，则返回空字符串 ""。 如果 S 中存在这样的子串，我们保证它是唯一的

分析：同样，采用双指针滑动窗口法，定义两个指针right和left，并都初始化为0，即字符串S的起始处。定义一个长度为256的数组window_arr来统计字符串T中的元素。如图，right和left移动的关键点分别为：

• 当当前窗口尚未完全包含T中的字母时，left不动，right右移，并计算此时的子串和窗口长度；
• 当当前窗口已经完全包含T中的字母时，right不动，left右移，并更新此时的子串和窗口长度；

string minWindow2(string s, string t){
  int count[256] = { 0 };
  int left = 0;
  int right = 0;
  int curLen = 0;
  int minLen = s.length();
  string res = "";
 
  for (int i = 0; i < t.length(); i++){
    count[t[i]]++;
  }
  while (right <= s.length()){
    if ((--count[s[right]]) >= 0){
      curLen++;
    }
    while (curLen == t.length()){
      if (right - left + 1 <= minLen){
        minLen = right - left + 1;
        res = s.substr(left, right - left + 1);
      }
      if (++count[s[left]] > 0){
        curLen--;
      }
      left++;
    }
    right++;
  }
  return res;
}

复制