两个指针和滑动窗口模式

小伙伴们有没有觉得学习文章很有意思？有意思就对了！今天就给大家带来《两个指针和滑动窗口模式》，以下内容将会涉及到，若是在学习中对其中部分知识点有疑问，或许看了本文就能帮到你！

双指针和滑动窗口模式

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

例如，给定一个 (-ve 和 +ve) 整数数组，找到大小为 k.

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

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

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

这个问题可以用模式2
解决 用于解决诸如查找 sum =k 的子串数量之类的问题。

• 这可以分解为

  • 查找 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){
                    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++;
        }

    }
}

今天关于《两个指针和滑动窗口模式》的内容介绍就到此结束，如果有什么疑问或者建议，可以在golang学习网公众号下多多回复交流；文中若有不正之处，也希望回复留言以告知！