Tag Archives: 滑动窗口

LeetCode Minimum Window Substring

76. Minimum Window Substring

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:

  • If there is no such window in S that covers all characters in T, return the empty string "".
  • If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

给两个字符串S和T,问S中是否存在一个子串,包括T中的所有字符,如果存在,输出最短的那个子串。

hard题,用双指针+滑动窗口。核心思想是找到滑动窗口[i,j),首先++j,加入右边界的字符;然后检查[i,j)是否能覆盖t;再然后++i,丢掉左边界的字符。

首先设置一个required数组,存储t中每个字符出现的次数,表示滑动窗口[i,j)需要覆盖的每个字符的次数。found表示需要找到的字符总数,如果found==t.size()表示滑动窗口能覆盖t。

首先检查右边界j,如果s[j]在t中,则++found。然后看看found==n?,如果是,则检查左边界,如果左边界s[i]在t中,则i++之后要–found。在窗口滑动过程中记录窗口最小长度。完整代码如下:

class Solution {
public:
	string minWindow(string s, string t) {
		int m = s.size(), n = t.size();
		vector<int> required(128, 0);
		for (int i = 0; i < n; ++i) {
			++required[t[i]];
		}

		int min_len = m + 1, start_id = 0, found = 0;
		int i = 0, j = 0;
		while (j < m) {
			--required[s[j]];
			if (required[s[j]] >= 0) { // s[j]在t中
				++found;
			}
			++j;

			while (found == n) {
				int cur_len = j - i;
				if (cur_len < min_len) {
					min_len = cur_len;
					start_id = i;
				}
				++required[s[i]];
				if (required[s[i]] > 0) --found;
				++i;
			}
		}
		if (min_len == m + 1) return "";
		else return s.substr(start_id, min_len);
	}
};

本代码提交AC,用时16MS。

今晚字节跳动三面,面试官问了一个此题的变种,即只给定了字符串s,要找s的一个子串,使得该子串能覆盖s中所有特异的字符,且子串越短越好。可以把面试问题转换为这个问题,即先遍历s,把s中的特异字符拼成一个字符串t,然后调用本题的解法。

LeetCode Maximum Number of Vowels in a Substring of Given Length

5417. Maximum Number of Vowels in a Substring of Given Length

Given a string s and an integer k.

Return the maximum number of vowel letters in any substring of s with length k.

Vowel letters in English are (a, e, i, o, u).

Example 1:

Input: s = "abciiidef", k = 3
Output: 3
Explanation: The substring "iii" contains 3 vowel letters.

Example 2:

Input: s = "aeiou", k = 2
Output: 2
Explanation: Any substring of length 2 contains 2 vowels.

Example 3:

Input: s = "leetcode", k = 3
Output: 2
Explanation: "lee", "eet" and "ode" contain 2 vowels.

Example 4:

Input: s = "rhythms", k = 4
Output: 0
Explanation: We can see that s doesn't have any vowel letters.

Example 5:

Input: s = "tryhard", k = 4
Output: 1

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters.
  • 1 <= k <= s.length

给定字符串s和长度k,问s中长度为k的子串中,包含最多元音字母的个数。

简单题,直接滑动窗口+双指针计数即可:

class Solution {
public:
	bool IsVol(const char &c) {
		return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
	}
	int maxVowels(string s, int k) {
		int ans = 0;
		int i = 0, j = k - 1, n = s.size();
		for (int k = i; k <= j; ++k) {
			if (IsVol(s[k]))++ans;
		}
		int cur = ans;
		while (j < n - 1) {
			++j;
			if (IsVol(s[j]))++cur;
			if (IsVol(s[i]))--cur;
			++i;
			ans = max(ans, cur);
		}
		return ans;
	}
};

本代码提交AC。

LeetCode Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.

In case there is no subarray satisfying the given condition return 0.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Constraints:

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

给定一个数组,问数组中一个连续的子数组内的最大值和最小值的差不超过limit的最长连续子数组的长度。

常规解法。使用DP求出任何一个子区间dp[i,j]的最大值和最小值,dp[i,j+1]的最大值和最小值只需要用nums[j]和dp[i,j]的最大值和最小值比较即可。完整代码如下:

class Solution {
public:
	int longestSubarray(vector<int>& nums, int limit) {
		int n = nums.size();
		int ans = 1; // 最小值是1

		for (int i = 0; i < n; ++i) {
			vector<int> dp_max(n, 0), dp_min(n, INT_MAX);
			dp_max[i] = dp_min[i] = nums[i];
			for (int len = 2; len <= n; ++len) {
				int j = i + len - 1;
				if (j >= n)break;
				dp_max[j] = max(dp_max[j - 1], nums[j]);
				dp_min[j] = min(dp_min[j - 1], nums[j]);
				int diff = dp_max[j] - dp_min[j];
				if (diff <= limit) {
					ans = max(ans, j - i + 1);
				}
				else {
					break;
				}
			}
		}
		return ans;
	}
};

很不幸,该代码的时间复杂度达到了O(n^2),在最后两个测试样例上TLE了。

比O(n^2)低的复杂度有O(nlgn)和O(n)。O(nlgn)排序好像无法求解,那么只有O(n)的方法了。此题本质上是一个滑动窗口的问题,可以用两个指针i和j,标记区间的起止位置。那么问题的关键就是如何快速求解到区间[i,j]的最大值和最小值。

我之前的方法是用DP提前算出来,但是DP的过程费时。使用优先队列priority_queue(最大堆、最小堆)可以得到当前区域的最大值和最小值,但是一旦差的绝对值超过limit,需要从优先队列中删除i所指元素时,priority_queue没有提供erase或者remove之类的接口,所以使用priority_queue无法达成目标。

提示使用multiset,我之前知道multiset内部使用红黑树结构,内部存储是有序的,而且提供了erase接口以供删除元素。但是我一直不确定如何获得multiset内部的最大值和最小值元素,虽然它内部是有序的,但我不确定程序员能否得到其有序列表。

后来看了multiset的API,里面明确说明了multiset默认是从小到大排序,而且其begin()指向最小值rbegin()指向最后一个元素,即最大值。所以multiset是一个功能很强大的容器,它不但可以实现堆的功能,还能查找、删除某个元素,比 priority_queue 更强大。

使用multiset的完整代码如下:

class Solution {
public:
    int longestSubarray(vector<int>& A, int limit) {
        int res = 0, n = A.size(), i = 0, j;
        multiset<int> m;
        for (j = 0; j < n; ++j) {
            m.insert(A[j]);
            if (*m.rbegin() - *m.begin() > limit)
                m.erase(m.find(A[i++]));
            else
                res=max(res,j-i+1);
        }
        return res;
    }
};

本代码提交AC,用时368MS。

另外,我们还可以指定multiset内部的排序规则,让其表现为最大堆或最小堆。

LeetCode Maximum Points You Can Obtain from Cards

1423. Maximum Points You Can Obtain from Cards

There are several cards arranged in a row, and each card has an associated number of points The points are given in the integer array cardPoints.

In one step, you can take one card from the beginning or from the end of the row. You have to take exactly k cards.

Your score is the sum of the points of the cards you have taken.

Given the integer array cardPoints and the integer k, return the maximum score you can obtain.

Example 1:

Input: cardPoints = [1,2,3,4,5,6,1], k = 3
Output: 12
Explanation: After the first step, your score will always be 1. However, choosing the rightmost card first will maximize your total score. The optimal strategy is to take the three cards on the right, giving a final score of 1 + 6 + 5 = 12.

Example 2:

Input: cardPoints = [2,2,2], k = 2
Output: 4
Explanation: Regardless of which two cards you take, your score will always be 4.

Example 3:

Input: cardPoints = [9,7,7,9,7,7,9], k = 7
Output: 55
Explanation: You have to take all the cards. Your score is the sum of points of all cards.

Example 4:

Input: cardPoints = [1,1000,1], k = 1
Output: 1
Explanation: You cannot take the card in the middle. Your best score is 1. 

Example 5:

Input: cardPoints = [1,79,80,1,1,1,200,1], k = 3
Output: 202

Constraints:

  • 1 <= cardPoints.length <= 10^5
  • 1 <= cardPoints[i] <= 10^4
  • 1 <= k <= cardPoints.length

给定一个数组,要从中选k个数,每次只能从左边选或从右边选,问选出的数的和最大是多少。

转换思路,无论从左边选多少个,从右边选多少个,剩余的数都是中间区域的某一段数。要使选出来的数和最大,则相当于要使剩下的连续区间的数和最小。所以可以设置一个大小为n-k的滑动窗口,求该滑动窗口的最小和,则用总和减去该最小和即为最终结果。

完整代码如下:

class Solution {
public:
	int maxScore(vector<int>& cardPoints, int k) {
		int sum = 0, n = cardPoints.size();
		for (int i = 0; i < n; ++i)sum += cardPoints[i];
		if (k == n)return sum;

		int min_window_sum = 0, i = 0, j = n - k - 1;
		for (int k = i; k <= j; ++k)min_window_sum += cardPoints[k];
		int cur_window_sum = min_window_sum;
		while (j < n) {
			if (j == n - 1)break;
			cur_window_sum = cur_window_sum + cardPoints[++j] - cardPoints[i++];
			min_window_sum = min(min_window_sum, cur_window_sum);
		}
		return sum - min_window_sum;
	}
};

本代码提交AC,用时152MS。

我之前的想法一直是正向思维,即模拟每次拿左边或右边,甚至还用DP来求解,但都无果。

看讨论区后还是很有启发,无论你当前这一步是拿左边还是右边,经过k轮之后的最终效果是,左边拿了连续的a的,右边拿了连续的k-a个。所以只需要对最终左边拿了几个进行DP建模,而无需模拟每一步是拿了左边还是右边。DP方法可看讨论区: https://leetcode.com/problems/maximum-points-you-can-obtain-from-cards/discuss/598111/Java-dp-solution(explanation-with-picture)

LeetCode Maximum Average Subarray I

LeetCode Maximum Average Subarray I Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value. Example 1:

Input: [1,12,-5,-6,50,3], k = 4
Output: 12.75
Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75
Note:
  1. 1 <= k <= n <= 30,000.
  2. Elements of the given array will be in the range [-10,000, 10,000].

给定一个数组,问长度为k的子数组的最大平均数是多少。简单题,因为平均数等于和除以k,k相同,也就相当于求长度为k的最长连续子串的和。 解法是维护一个长度为k的滑动窗口,求滑动窗口内的最大连续子数组的和,然后除以k。 代码如下: [cpp] class Solution { public: double findMaxAverage(vector<int>& nums, int k) { int n = nums.size(); if (n < k)return 0; int i = 0, sum = 0, ans = INT_MIN; for (int j = 0; j < k; ++j)sum += nums[j]; for (int j = k; j < n; ++j) { ans = max(ans, sum); sum += nums[j] – nums[i]; ++i; } ans = max(ans, sum); return ans / double(k); } }; [/cpp] 本代码提交AC,用时176MS。]]>

LeetCode Contains Duplicate III

220. Contains Duplicate III

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3 Output: false

给定一个数组,问是否存在两个相距k之内的差的绝对值在t之内的数。
这个题有点难度,是LeetCode Contains Duplicate II的升级版。
首先,要求距离在k之内,所以想到维护一个长度为k的滑动窗口,在这个滑动窗口内判断是否有差的绝对值在t之内的两个数。
具体参考讨论区。用一个set来保存长度为k的滑动窗口window,每次往前滑动一格,如果窗口大于k了,则删除窗口左边的元素。对于即将进入窗口的数nums[i],我们需要判断窗口内是否存在一个x,使得$|x-nums[i]|\leq t$,展开就是$nums[i]-t\leq x\leq t+nums[i]$。
由于set内部是有序的树结构,所以可以用set.lower_bound直接判断大于等于$nums[i]-t$的数x是否在window中。如果在的话,我们再判断是否满足$x\leq t+nums[i]$,这个式子等价于$x-nums[i]\leq t$,为什么要这么写呢,因为nums[i]有可能是INT_MAX或者INT_MIN,为了防止溢出,需要把相关的操作数转换为long long。
完整代码如下:

typedef long long ll;
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t)
    {
        set<ll> window;
        for (int i = 0; i < nums.size(); ++i) {
            if (i > k)
                window.erase(nums[i – k – 1]); // 删除窗口左边的元素
            auto it = window.lower_bound(ll(nums[i]) – t); // x>=nums[i]-t
            if (it != window.end() && *it – nums[i] <= t)
                return true; // x<=nums[i]+t
            window.insert(nums[i]);
        }
        return false;
    }
};

本代码提交AC,用时19MS。

LeetCode Longest Repeating Character Replacement

LeetCode Longest Repeating Character Replacement Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations. Note: Both the string’s length and k will not exceed 104. Example 1:

Input:
s = "ABAB", k = 2
Output:
4
Explanation:
Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input:
s = "AABABBA", k = 1
Output:
4
Explanation:
Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

给定一个字符串s,可以把s中最多k个字符换成另一个字符,问这样做之后,最大能得到多长的重复字符的字符串。 比如样例一s=”ABAB”,k=2,把两个A都改为B之后,所有字符都变成了B,长度为4。 本题使用滑动窗口来解。每次我们统计窗口内出现频率最多的字符,那么最好的办法就是把窗口内其他字符全换成最高频的字符,条件就是其他字符的数量要不超过k,这样替换的次数才不会超过k。 在滑动窗口的时候,如果其他字符的数量超过k了,则需要缩减窗口大小,也就是把窗口左端往右滑。 代码如下: [cpp] class Solution { public: int characterReplacement(string s, int k) { int ans = 0, n = s.size(); vector<int> count(26, 0); int start = 0; for (int end = 0; end < n; ++end) { ++count[s[end] – ‘A’]; while (end – start + 1 – *max_element(count.begin(), count.end()) > k) { –count[s[start++] – ‘A’]; } ans = max(ans, end – start + 1); } return ans; } }; [/cpp] 本代码提交AC,用时29MS。渐进复杂度应该是O(n^2)的。 讨论区还有O(n)的方法,但是我看了好久都没理解,为啥max不会减少,为啥返回的直接是s.length()-start。]]>

LeetCode Permutation in String

LeetCode Permutation in String Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string’s permutations is the substring of the second string. Example 1:

Input:s1 = "ab" s2 = "eidbaooo"
Output:True
Explanation: s2 contains one permutation of s1 ("ba").
Example 2:
Input:s1= "ab" s2 = "eidboaoo"
Output: False
Note:
  1. The input strings only contain lower case letters.
  2. The length of both given strings is in range [1, 10,000].

给定两个字符串s1和s2,问s1的排列是否是s2的子串。 暴力方法是枚举s2的每个字符,如果在s1中,则在s2中取等长的子串,hash判断s2的子串和s1是否是同一个串的不同排列。 代码如下: [cpp] class Solution { public: bool checkInclusion(string s1, string s2) { int n = s1.size(), m = s2.size(); if (n > m)return false; unordered_map<char, int> hash1; for (int i = 0; i < n; ++i)++hash1[s1[i]]; for (int i = 0; i < m; ++i) { if (hash1.find(s2[i]) != hash1.end()) { if (i + n <= m) { unordered_map<char, int> hash2; for (int j = i; j < i + n; ++j)++hash2[s2[j]]; if (hash1 == hash2)return true; } } } return false; } }; [/cpp] 本代码提交AC,用时1365MS。 优化方法是使用滑动窗口方法,假设s1的长度为n。先hash s1,再在s2中开长度为n的窗口,判断窗口内的子串hash是否和s1的hash相等,相等则返回tru,否则窗口向右滑动一格,即增加右边一个字符频率,同时减掉左边一个字符频率,如此循环。 代码如下: [cpp] class Solution { public: bool checkInclusion(string s1, string s2) { int n = s1.size(), m = s2.size(); if (n > m)return false; vector<int> hash1(26, 0), hash2(26, 0); for (int i = 0; i < n; ++i) { ++hash1[s1[i] – ‘a’]; ++hash2[s2[i] – ‘a’]; } if (hash1 == hash2)return true; for (int i = n; i < m; ++i) { ++hash2[s2[i] – ‘a’]; –hash2[s2[i – n] – ‘a’]; if (hash1 == hash2)return true; } return false; } }; [/cpp] 本代码提交AC,用时13MS。]]>

LeetCode Contains Duplicate II

219. Contains Duplicate II

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1
Output: true

Example 3:

Input: nums = [1,2,3,1,2,3], k = 2 Output: false

本题是LeetCode Contains Duplicate的升级版,要求是判断是否有距离不超过k的两个相同的数。
首先想到暴力方法,一种是直接两层长度为n的循环,判断是否有距离不超过k的两个相等的数,另一种是外层循环为n,内层只要循环长度k,因为即使超过k有相等数的,也不符合题意。尝试之后显然超时。
然后我想到了另一种方法,把数组中所有相同数字的下标都放到一个桶里,后续再在这个桶里看是否有距离不超过k的两个下标对;如果桶里只有一个下标,说明这个下标对应的数没有重复出现,直接continue。完整代码如下:

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        if (nums.size() == 0)
            return false;
        unordered_map<int, int> hash_table;
        int distinct_cnt = 1; // 相异元素的个数
        vector<vector<int> > duplicate_indices = { {} }; // 跳过第0个桶
        for (int i = 0; i < nums.size(); i++) {
            if (hash_table[nums[i]] == 0) {
                hash_table[nums[i]] = distinct_cnt++;
                duplicate_indices.push_back({ i });
            }
            else {
                duplicate_indices[hash_table[nums[i]]].push_back(i);
                // 把相同元素的下标都放到一个桶里
            }
        }
        for (int i = 1; i < duplicate_indices.size(); i++) {
            // 查每个桶
            if (duplicate_indices[i].size() < 2)
                continue;
            for (int u = 0; u < duplicate_indices[i].size() – 1; u++) {
                for (int v = u + 1; v < duplicate_indices[i].size(); v++) {
                    if (duplicate_indices[i][v] – duplicate_indices[i][u] <= k)
                        return true;
                }
            }
        }
        return false;
    }
};

本代码提交AC,用时46MS。
后来看欣欣的解法LeetCode Contains Duplicate II,发现这个解法好厉害啊,用到了高级的unordered_set,之前只用过unordered_map,赶紧来学习一下。
她的思路是这样的,题目要求相同元素的距离不超过k,则我们维护一个长度为k的滑动窗口,把这个窗口里的所有数都hash到unordered_set里,后续每来一个元素,去这个hash_set里查之前是否出现过,因为我们的hash_set里只保留了前k个元素,所以如果hash_set查到了,他们的距离肯定是不超过k的。这种解法真是漂亮!完整代码如下:

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        if (nums.size() == 0 || k <= 0)
            return false;
        if (k >= nums.size())
            k = nums.size() – 1;
        unordered_set<int> hash_set;
        for (int i = 0; i < nums.size(); i++) {
            if (i > k)
                hash_set.erase(nums[i – k – 1]); // 滑动窗口,删掉窗口第一个元素
            if (hash_set.find(nums[i]) != hash_set.end())
                return true;
            hash_set.insert(nums[i]); // 把新元素插入窗口
        }
        return false;
    }
};

本代码提交AC,用时29MS,果然比我的速度快,厉害~
二刷。用一个hash表记录每个数最近出现的下标,如果新来一个数,之前在hash表中出现过,则看看下标之差是否小于等于k,是则返回true;否则更新hash。
思路非常简单,代码如下:

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k)
    {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i) {
            if (hash.find(nums[i]) != hash.end() && i – hash[nums[i]] <= k)
                return true;
            hash[nums[i]] = i;
        }
        return false;
    }
};

本代码提交AC,用时35MS。