双指针和滑动窗口模式
模式 1：常量窗口（如 window = 4 或某个整数值）
例如，给定一个 (-ve 和 +ve) 整数数组，找到大小为 k.
的连续窗口的最大总和模式 2：（可变窗口大小）具有 的最大子数组/子字符串示例：总和
模式 3： 的子数组/子字符串的数量就像 sum=k。
这个问题很难解决，因为何时扩展（右++）或何时收缩（左++）变得很困难。
这个问题可以用模式2
解决
用于解决诸如查找 sum =k 的子串数量之类的问题。
这可以分解为
模式4：找到最短/最小窗口
模式 2 的不同方法：
示例：总和
的最大子数组
public class Sample{
public static void main(String args[]){
n = 10;
int arr[] = new int[n];
//Brute force approach for finding the longest subarray with sum <=k
//tc : O(n^2)
int maxlen=0;
for(int i =0;i<arr.length;i++){
int sum =0;
for(int j = i+1;j<arr.length;j++){
sum+=arr[j];
if(sum<=k){
maxLen = Integer.max(maxLen, j-i+1);
}
else if(sum > k) break; /// optimization if the sum is greater than the k, what is the point in going forward?
}
}
使用两个指针和滑动窗口的更好方法
//O(n+n) in the worst case r will move from 0 to n and in the worst case left will move from 0 0 n as well so 2n
int left = 0;
int right =0;
int sum = 0;
int maxLen = 0;
while(right<arr.length){
sum+=arr[right];
while(sum > k){
sum = sum-arr[left];
left++;
}
if(sum <=k){
maxLen = Integer.max(maxLen, right-left+1); //if asked to print max subarray length,we print maxLen else asked for printing the subarray keep track of
// left and right in a different variable
}
right++;
}
最佳方法：
我们知道，如果找到子数组，我们将其长度存储在 maxLen 中，但是在添加 arr[right] 时，如果总和大于 k，那么当前我们通过执行 sum = sum-arr[left] 和 left++ 来向左收缩。
我们知道当前的最大长度是maxLen，如果我们继续缩小左索引，我们可能会得到另一个满足条件（<=k）的子数组，但长度可能小于当前的maxLen，那么我们不会更新maxLen，直到我们找到另一个满足条件并且也具有 len > 的子数组。 maxLen，则仅更新 maxLen。
当子数组不满足条件 (<=k)int left = 0 时，最佳方法是仅在子数组长度大于 maxLen 时收缩左侧。
int right =0;
int sum = 0;
int maxLen = 0;
while(right<arr.length){
sum+=arr[right];
if(sum > k){// this will ensure that the left is incremented one by one (not till the sum<=k because this might reduce the length i.e right-left+1 which will not be taken into consideration)
sum = sum-arr[left];
left++;
}
if(sum <=k){
maxLen = Integer.max(maxLen, right-left+1); //if asked to print max subarray length,we print maxLen else asked for printing the subarray keep track of
// left and right in a different variable
}
right++;
}
}
}
以上是两个指针和滑动窗口模式的详细内容。更多信息请关注PHP中文网其他相关文章！
