Tag Archives: 滑动窗口

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。
代码如下:

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);
	}
};

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

LeetCode Contains Duplicate III

LeetCode 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.


给定一个数组,问是否存在两个相距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了,则需要缩减窗口大小,也就是把窗口左端往右滑。
代码如下:

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;
	}
};

本代码提交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是否是同一个串的不同排列。
代码如下:

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;
	}
};

本代码提交AC,用时1365MS。
优化方法是使用滑动窗口方法,假设s1的长度为n。先hash s1,再在s2中开长度为n的窗口,判断窗口内的子串hash是否和s1的hash相等,相等则返回tru,否则窗口向右滑动一格,即增加右边一个字符频率,同时减掉左边一个字符频率,如此循环。
代码如下:

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;
	}
};

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

LeetCode Contains Duplicate II

LeetCode 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 difference between i and j is at most k.


本题是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。