双指针滑动窗口法解析及LeetCode相关题解
双指针滑动窗口法解析及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;
}