【算法技巧】数组连续子集操作---滑动窗口使用

题目

已知一个数组arr=[-5,2,7,4,3,6]，求长度为k的连续连续子集和中最大值

解题思路

想法1

首先是比较容易想到的思路，即利用双层循环进行遍历，代码如下：

int maxSum(vector<int> &arr,int k){
	//首先进行判断，如果数组长度不足k，直接返回0
	int n = arr.size();
	if(n < k) return 0;
	//定义全局变量记录最大值，两重循环遍历完整个数组
	int ans = INT_MIN;
	for(int i = 0;i <= n - k;i++){
		int sum = 0;
		for(int j = 0;j < k;j++){
			sum += arr[i + j];
		}
		ans = max(ans,sum);
	}
	return ans;
}

虽然这种思路容易被想到，但是时间复杂度过高，是O(n²)，所以介绍今天的重点，滑动窗口求连续长度子数组和最大值

想法2

既然要求长度为k的子数组元素之和，那么可以看出，求arr[0]到arr[k]的元素之和与求arr[1]到arr[k+1]，中间有重复的arr[1]至arr[k]，所以这个思路就是利用中间不变性，只需要考虑收尾元素即可，代码如下：

int maxSum(vector<int> &arr,int k){
	//首先进行判断，如果数组长度不足k，直接返回0
	int n = arr.size();
	if(n < k) return 0;
	//定义全局变量记录最大值，两重循环遍历完整个数组
	int ans = INT_MIN;
	// 区别只在循环这里，首先求得从下标0开始长度为K的子数组长度
	int sum = 0;
	for(int i = 0;i <k;i++){
		sum += arr[i];
	}
	ans = max(ans,sum);
	// 后面需要做的就是去掉头，加上尾，中间保持不动即可
	for(int i = k;i < n;i++){
		sum = sum - arr[i - k] + arr[i];
		ans = max(ans,sum);
	}
	return ans;
} 

通过利用局部不变性，可将时间复杂度降为O(n)

拓展

利用滑动窗口，还可以求连续子集的如下操作

• 连续子集元素均值
• 连续子集元素和/均值大于某个阈值的情况等

总而言之，涉及到数组元素是数字且求连续子集的相关操作时，都可以考虑使用滑动窗口