双指针和滑动窗口模式

模式 1：常量窗口（如 window = 4 或某个整数值）

例如，给定一个（-ve 和 ve）整数数组，找到大小为 k 的连续窗口的最大和.

模式2：（可变窗口大小）具有的最大子数组/子字符串示例：sum

• 方法：
  • 蛮力： 生成所有可能的子数组并选择最大长度的子数组 sum
• 最佳/最佳： 利用两个指针和滑动窗口将时间复杂度降低到O(n)

模式3：子数组/子字符串的数量，其中像sum=k。
这个问题很难解决，因为何时扩展（右）或何时收缩（左）变得很困难。

这个问题可以用模式2
来解决 用于解决诸如查找 sum =k.

• 这可以细分为

  • 查找 sum 的子数组
  • 查找sum

模式4：找到最短/最小窗口

模式 2 的不同方法：
示例：sum

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



最佳方法：

我们知道，如果找到子数组，我们将其长度存储在 maxLen 中，但是在添加 arr[right] 时，如果总和大于 k，那么当前我们通过执行 sum = sum-arr[left] 和 left 来向左收缩。 

我们知道当前的最大长度是maxLen，如果我们继续缩小左索引，我们可能会得到另一个满足条件（ maxLen 的子数组，则仅更新 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