双指针和滑动窗口模式
模式 1：常量窗口（如 window = 4 或某个整数值）
例如，给定一个 (-ve 和 +ve) 整数数组，找到大小为 k.
的连续窗口的最大总和
模式 2：（可变窗口大小）具有 的最大子数组/子字符串示例：sum <=k.
方法：蛮力：生成所有可能的子数组并选择最大长度的子数组 sum <=k （时间复杂度为 $o(n^2)$。最佳/最佳：利用两个指针和滑动窗口将时间复杂度降低到o(n)
模式 3：没有子数组/子字符串，其中 就像 sum=k。
这个问题很难解决，因为何时扩展（右++）或何时收缩（左++）变得很困难。
这个问题可以用模式2
解决用于解决诸如查找 sum =k 的子串数量之类的问题。
这可以分解为
协和·太初
国内首个针对罕见病领域的AI大模型
38 查看详情 查找 sum<=k —-x 的子数组查找子数组 sum<=k-1—-y那么结果将是 x-y = 答案
模式 4：找到最短/最小窗口
模式 2 的不同方法：
示例：最大子数组 sum<=k
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) 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 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，如果我们继续缩小左索引，我们可能会得到另一个满足条件的子数组（ maxlen 的子数组，则仅更新 maxlen。
当子数组不满足条件 (<=k)int left = 0 时，最佳方法是仅在子数组长度大于 maxlen 时收缩左侧。
int right =0; int sum = 0; int maxLen = 0; while(right 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++; } }}
以上就是两个指针和滑动窗口模式的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/479307.html
微信扫一扫 
支付宝扫一扫 
