1. Pattern: Sliding window,滑动窗口类型
滑动窗口类型的题目经常是用来执行数组或是链表上某个区间(窗口)上的操作。比如找最长的全为1的子数组长度。滑动窗口一般从第一个元素开始,
一直往右边一个一个元素挪动。当然了,根据题目要求,我们可能有固定窗口大小的情况,也有窗口的大小变化的情况。
该图中,我们的窗子不断往右一格一个移动
下面是一些我们用来判断我们可能需要上滑动窗口策略的方法:
这个问题的输入是一些线性结构:比如链表呀,数组啊,字符串啊之类的
让你去求最长/最短子字符串或是某些特定的长度要求
经典题目:
Maximum Sum Subarray of Size K (easy)
/*
查找最大子数组和
Find maximum(or minimum) sum of a subarray of size k
Last Updated : 09 - 05 - 2020
Given an array of integers and a number k, find maximum sum of a subarray of size k.
Examples :
Input: arr[] = { 100, 200, 300, 400 }
k = 2
Output : 700
Input : arr[] = { 1, 4, 2, 10, 23, 3, 1, 0, 20 }
k = 4
Output : 39
We get maximum sum by adding subarray{ 4, 2, 10, 23 }
of size 4.
Input : arr[] = { 2, 3 }
k = 3
Output : Invalid
There is no subarray of size 3 as size of whole
array is 2.
*/
//O(n) solution for finding maximum sum of a subarray of size k
#include <iostream>
using namespace std;
//Return s maximum sum in a subarray of size k.
int maxSum(int arr[], int n, int k)
{
// k must be greater
if (n < k)
{
cout << "Invalid";
return -1;
}
//Compute sum of first window of size k
int res = 0;
for (int i = 0; i < k; i++)
res += arr[i];
//Compute sums of remaining windows by removing first element of previous
//window and adding last element of current window.
int curr_sum = res;
for (int i = k; i < n; i++) {
curr_sum += arr[i] - arr[i - k];
res = max(res, curr_sum);
}
return res;
}
//Drier code
int main() {
int arr[] = { 1,4,2,10,2,3,1,0,20 };
int k = 4;
int n = sizeof(arr) / sizeof(arr[0]);
cout << maxSum(arr, n, k);
return 0;
}
/*
求出所有的连续子数组
Subarray/Substring vs Subsequence and Programs to Generate them
Last Updated: 18-09-2018
Subarray/Substring
A subbarray is a contiguous part of array. An array that is
inside another array. For example, consider the array [1, 2, 3, 4],
There are 10 non-empty sub-arrays.
The subbarays are (1), (2), (3), (4), (1,2), (2,3), (3,4), (1,2,3), (2,3,4) and (1,2,3,4).
In general, for an array/string of size n, there are n*(n+1)/2 non-empty subarrays/subsrings.
All Non-empty Subarrays
1
1 2
1 2 3
1 2 3 4
2
2 3
2 3 4
3
3 4
4
*/
#include <stdio.h>
using namespace std;
//print all subarrays in arr[0...n-1]
void subArray(int arr[], int n)
{
//pick start point
for (int i = 0; i < n; i++)
{
//pick ending point
for(int j = i; j < n; j++)
{
//print subarray between current starting
for (int k = j; k <= j; k++) {
cout << arr[k] << ",";
}
cout << endl;
}
}
}
//Driver program
int main()
{
int arr[] = { 1,2,3,4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "All Non-empty Subarray
";
subArray(arr,n);
return 0;
}
Smallest Subarray with a given sum (easy)
Longest Substring with K Distinct Characters (medium)
Fruits into Baskets (medium)
No-repeat Substring (hard)
Longest Substring with Same Letters after Replacement (hard)
Longest Subarray with Ones after Replacement (hard)
一,Maximum Sum Subarray of Size K (easy)
Given an array arr of size N and an integer K, the task is to find the maximum sum subarray of size k among all contiguous sub-array (considering circular subarray also).
Examples:Input: arr = {18, 4, 3, 4, 5, 6, 7, 8, 2, 10}, k = 3
Output:
max circular sum = 32,start index = 9,end index = 1,Explanation:Maximum Sum = 10 + 18 + 4 = 32
解答1:
//C++ program to find maximum circular
//subarray sum of size k
#include <bits/stdc++.h>
using namespace std;
//Function to calculate
//maximum sum
void maxCircularSum(int arr[], int n, int k)
{
//k must be greater
if (n < k) {
cout << "Invalid";
return;
}
int sum = 0, start = 0, end = k - 1;
//calculate the sum of first k elements;
for (int i = 0; i < k; i++)
{
sum += arr[i];
}
int ans = sum;
for (int i = k; i < n + k; i++)
{
//add current element to sum
//and substract the first element
//of the previous window.
sum += arr[i % n] - arr[(i - k) % n];
if (sum > ans) {
ans = sum;
start = (i - k + 1) % n;
end = i % n;
}
}
cout << "Max circular sum=" << ans << endl;
cout << "start index=" << start << "
end index=" << end << endl;
}
//Driver Code
int main()
{
int arr[] = { 18,4,3,4,5,6,7,8,2,10 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
maxCircularSum(arr,n,k);
return 0;
}