Java 滑动窗口算法详解及通用实现模板案例示范

🕗 发布于 2024-10-18 00:17 java 算法 开发语言 面试架构

1. 引言

在解决一些子数组或子字符串相关的问题时，滑动窗口算法（Sliding Window Algorithm）是一种非常高效的算法策略。它能帮助我们避免使用暴力搜索的方式，减少时间复杂度，尤其在处理大规模数据时表现出色。滑动窗口算法的核心思想是通过一对边界指针来动态调整子数组或子字符串的范围，从而减少不必要的重复计算。
本文将详细讲解滑动窗口算法的原理、通用实现模板及其应用场景，并结合实际案例进行示范。

2. 滑动窗口算法的基本原理

滑动窗口算法适用于处理数组或字符串中的连续子数组（子字符串）问题。其基本思路是通过固定一个边界（通常是左边界），然后滑动另一个边界（通常是右边界），逐步扩大窗口的范围。当满足特定条件时，再调整窗口的左边界，从而减少窗口的范围。

滑动窗口的关键步骤包括：

初始化两个指针，表示窗口的左右边界。
移动右指针，扩大窗口，直到满足问题要求的条件。
当条件不再满足时，移动左指针，缩小窗口，直到再次满足条件。
不断重复该过程，直到右指针遍历完整个数组或字符串。

2.1 滑动窗口的应用场景

滑动窗口算法常用于解决以下问题：

寻找最大或最小子数组的和：例如寻找数组中和为特定值的连续子数组。
最长/最短子字符串：例如寻找不含重复字符的最长子字符串。
频率统计问题：例如在字符串中查找包含所有目标字符的最小子串。
网络吞吐量：滑动窗口可以模拟网络流量控制，动态调整传输的数据包大小。

3. 滑动窗口的通用实现模板

滑动窗口算法的实现可以分为固定窗口大小和动态窗口大小两种常见模式。下面展示滑动窗口的通用实现模板。

3.1 固定大小的滑动窗口模板

这种方式适用于问题需要固定长度的子数组或子字符串。例如：查找长度为 k 的子数组的最大和。

public class FixedSlidingWindow {
    /**
     * 固定大小的滑动窗口算法
     * @param arr 输入数组
     * @param k 窗口的大小
     * @return 窗口内最大和
     */
    public static int maxSum(int[] arr, int k) {
        int maxSum = 0;
        int windowSum = 0;

        // 计算第一个窗口的和
        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }

        maxSum = windowSum;

        // 滑动窗口，计算每次新窗口的和
        for (int i = k; i < arr.length; i++) {
            windowSum += arr[i] - arr[i - k];
            maxSum = Math.max(maxSum, windowSum);
        }

        return maxSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 2, 5, 7, 2, 4, 6, 3};
        int k = 3;
        System.out.println("固定窗口的最大和为: " + maxSum(arr, k));
    }
}

3.2 动态大小的滑动窗口模板

动态滑动窗口用于处理可变窗口大小的问题，例如寻找和为某个值的最小连续子数组。

public class DynamicSlidingWindow {
    /**
     * 动态大小的滑动窗口算法
     * @param arr 输入数组
     * @param target 目标和
     * @return 符合条件的最小子数组长度
     */
    public static int minSubArrayLen(int[] arr, int target) {
        int left = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;

        for (int right = 0; right < arr.length; right++) {
            sum += arr[right];

            // 当窗口内的和大于等于目标值时，尝试缩小窗口
            while (sum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= arr[left];
                left++;
            }
        }

        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 2, 4, 3};
        int target = 7;
        System.out.println("最小子数组长度: " + minSubArrayLen(arr, target));
    }
}

3.3 滑动窗口的时间复杂度分析

滑动窗口的时间复杂度通常为 O(n)，其中 n 是数组或字符串的长度。这是因为每个元素最多被访问两次：一次是右指针扩展窗口时，另一次是左指针缩小窗口时。因此，滑动窗口算法比暴力算法更高效。

4. 案例分析：滑动窗口算法在电商系统中的应用

在电商系统中，滑动窗口算法有许多实际应用场景，特别是在分析交易数据、用户行为和优化库存管理等方面。以下是几个具体的案例分析。

4.1 案例 1：查找连续订单中的最大销售额

在电商系统中，我们可以使用滑动窗口算法查找一段连续时间内（例如过去 7 天）的最大销售额。通过固定大小的滑动窗口，快速找到销售额最高的时间段。

public class MaxSales {
    /**
     * 计算固定天数内的最大销售额
     * @param sales 每天的销售额
     * @param k 窗口大小（天数）
     * @return 最大销售额
     */
    public static int maxSales(int[] sales, int k) {
        int maxSales = 0;
        int windowSum = 0;

        // 计算初始窗口的销售额
        for (int i = 0; i < k; i++) {
            windowSum += sales[i];
        }

        maxSales = windowSum;

        // 滑动窗口，找出最大销售额
        for (int i = k; i < sales.length; i++) {
            windowSum += sales[i] - sales[i - k];
            maxSales = Math.max(maxSales, windowSum);
        }

        return maxSales;
    }

    public static void main(String[] args) {
        int[] sales = {200, 400, 300, 600, 700, 500, 100, 900};
        int k = 3;
        System.out.println("连续" + k + "天的最大销售额为: " + maxSales(sales, k));
    }
}

4.2 案例 2：查找满足最低库存要求的最小天数

在库存管理中，滑动窗口算法可以用于查找满足某个最低库存要求的最小天数。例如，某个商品的总库存要达到 1000 件，系统可以使用滑动窗口算法快速找到连续库存满足条件的最小时间范围。

public class MinDaysForStock {
    /**
     * 查找满足最低库存要求的最小天数
     * @param stocks 每天的库存量
     * @param target 目标库存
     * @return 符合条件的最小天数
     */
    public static int minDaysForStock(int[] stocks, int target) {
        int left = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;

        for (int right = 0; right < stocks.length; right++) {
            sum += stocks[right];

            // 当窗口内的库存总量大于等于目标时，尝试缩小窗口
            while (sum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= stocks[left];
                left++;
            }
        }

        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        int[] stocks = {100, 200, 300, 400, 500, 600, 700};
        int target = 1000;
        System.out.println("满足目标库存的最小天数为: " + minDaysForStock(stocks, target));
    }
}

5. 滑动窗口的时序图

在这里插入图片描述

6. 滑动窗口的常见问题

6.1 窗口边界问题

问题描述

滑动窗口算法最常见的问题之一是边界检查。由于窗口在不断滑动时，指针（特别是右指针）会动态扩展，导致容易越界，特别是在数组的边缘进行扩展时。例如，当我们向右扩展窗口，试图访问超出数组长度的元素时，就会抛出数组越界异常。

示例代码

以下是一个简单的滑动窗口算法，试图查找数组中和为某个目标值的最小连续子数组。如果我们在处理边界时不仔细，可能会导致访问越界。

public class SlidingWindowBoundaryError {

    public static int findMinSubArrayLen(int[] arr, int target) {
        int left = 0, sum = 0, minLength = Integer.MAX_VALUE;

        for (int right = 0; right < arr.length; right++) {
            sum += arr[right];

            while (sum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= arr[left++];
            }
        }

        // 返回结果时忘记检查是否存在符合条件的子数组
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 4};
        int target = 7;
        System.out.println(findMinSubArrayLen(arr, target)); // 可能导致返回错误结果
    }
}

解决方案

在处理滑动窗口时，首先需要在右指针或左指针滑动的每一步都进行边界检查，确保指针不越界。其次，在算法结束后需要确保是否真正找到了符合条件的子数组。如果没有，则应返回特殊的标志（例如 0 或其他值），而不是默认的最大长度。

public class SlidingWindowBoundarySolution {

    public static int findMinSubArrayLen(int[] arr, int target) {
        int left = 0, sum = 0, minLength = Integer.MAX_VALUE;

        for (int right = 0; right < arr.length; right++) {
            sum += arr[right];

            while (sum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= arr[left++];
            }
        }

        // 检查是否找到了符合条件的子数组
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 4};
        int target = 7;
        System.out.println(findMinSubArrayLen(arr, target)); // 返回 2，正确结果
    }
}

通过在最后一步检查结果，我们避免了边界问题带来的错误结果。

6.2 窗口的初始化问题

问题描述

滑动窗口的另一个常见问题是窗口初始化时的错误，特别是处理浮点数、负数或不一致的数据类型时。例如，在查找和为某个目标的连续子数组时，如果初始窗口没有正确计算，可能会导致算法在一开始就返回错误的结果。

示例代码

考虑以下算法，它试图找到和为 target 的最小连续子数组。如果初始化窗口时没有正确处理，可能会导致结果不准确。

public class SlidingWindowInitializationError {

    public static int minSubArrayLen(int target, int[] arr) {
        int left = 0, sum = 0;
        int minLength = Integer.MAX_VALUE;

        // 错误：窗口未正确初始化
        if (arr == null || arr.length == 0) {
            return 0;
        }

        for (int right = 0; right < arr.length; right++) {
            sum += arr[right];

            while (sum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= arr[left++];
            }
        }

        // 错误：忘记处理无解的情况
        return minLength;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 2, 4, 3};
        int target = 7;
        System.out.println(minSubArrayLen(target, arr)); // 错误：可能返回无效结果
    }
}

解决方案

在实现滑动窗口算法时，务必确保在操作窗口之前进行正确的初始化。检查输入数组是否为空或长度为零，并确保算法能处理无解的情况。

public class SlidingWindowInitializationSolution {

    public static int minSubArrayLen(int target, int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int left = 0, sum = 0;
        int minLength = Integer.MAX_VALUE;

        for (int right = 0; right < arr.length; right++) {
            sum += arr[right];

            while (sum >= target) {
                minLength = Math.min(minLength, right - left + 1);
                sum -= arr[left++];
            }
        }

        // 处理无解的情况
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 2, 4, 3};
        int target = 7;
        System.out.println(minSubArrayLen(target, arr)); // 返回 2，正确结果
    }
}

通过正确初始化输入并处理无解情况，算法能够稳定地返回正确的结果。

6.3 窗口缩小策略问题

问题描述

滑动窗口算法的另一个难点在于如何正确缩小窗口。通常，当窗口中的条件不再满足时，需要适时移动左指针缩小窗口。然而，什么时候缩小窗口，缩小到何种程度是一个关键点。如果缩小策略不正确，可能会导致算法错误。

示例代码

考虑一个场景，我们试图查找字符串中不包含重复字符的最长子字符串。滑动窗口会扩大和缩小，以保持子字符串不包含重复字符。然而，如果缩小策略错误，可能会导致漏掉符合条件的解。

import java.util.HashSet;

public class SlidingWindowShrinkError {

    public static int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int left = 0, maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }

            set.add(s.charAt(right));
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(s)); // 预期返回 3，但缩小策略错误时可能返回较小值
    }
}

解决方案

正确的缩小策略应当保证每次窗口缩小时，保持窗口内的元素满足问题要求。例如，对于不含重复字符的最长子字符串问题，在缩小窗口时应确保左指针指向不再包含重复字符的位置。

import java.util.HashSet;

public class SlidingWindowShrinkSolution {

    public static int lengthOfLongestSubstring(String s) {
        HashSet<Character> set = new HashSet<>();
        int left = 0, maxLength = 0;

        for (int right = 0; right < s.length(); right++) {
            // 当遇到重复字符时，移动左指针缩小窗口
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }

            set.add(s.charAt(right));
            maxLength = Math.max(maxLength, right - left + 1);
        }

        return maxLength;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        System.out.println(lengthOfLongestSubstring(s)); // 正确返回 3
    }
}

通过合理地移动左指针，确保窗口中的元素符合要求，我们可以确保滑动窗口算法的正确性。

原文地址：https://blog.csdn.net/weixin_39996520/article/details/143028344

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：【c++篇】:初识c++--编程新手的快速入门之道（二）
下一篇：吴恩达深度学习笔记（6）

【Vue.js设计与实现】第三篇第10章：渲染器-双端 Diff 算法-阅读笔记
本章我们介绍了双端 Diff 算法的原理及其优势。双端 Diff 算法指的是，在新旧两组子节点的四个端点之间分别进行比较，并试图找到可复用的节点。相比简单 Diff 算法，双端 Diff 算法的优势在
阅读更多2024-10-19
Flutter Scaffold组件
想象一下，你正在建造一座房子，每个房间都代表着应用用户界面的不同部分。在Flutter中，这些房间被称为widget。就像在房子里，每个房间都有不同的家具和装饰一样，Flutter widgets是构
阅读更多2024-10-19
rootless模式下istio ambient鉴权策略
在rootless模式下的kind k8s集群，兼容istio ambient鉴权策略设置。
阅读更多2024-10-19
flutter assets配置加载本地图片报错
需要注意的是，目录批量指定并不递归，只有该目录下的文件可以被包括，如果有子目录，需要单独声明子目录下的文件‌。目录下的文件都将被包含进来，而不需要逐个列出每个文件‌。这里着重强调的最新版的flutte
阅读更多2024-10-19
预训练模型通过 prompt（提示）生成的“软标签”是什么
软标签（Soft Label）通常指的是模型预测结果中输出的概率分布。例如，如果一个分类任务中有3个类别，模型的输出可能是：这意味着模型认为输入数据属于类别1的概率是70%，类别2是20%，类别3是1
阅读更多2024-10-19
OpenAI Prompt generation - 生成和优化Prompt的Prompt
OpenAI Prompt generation - 生成和优化Prompt的Prompt
阅读更多2024-10-19
【4.10】图搜索算法-BFS和DFS解电话号码的字母组合
给定一个仅包含数字2-9的字符串，返回所有它能表示的字母组合。答案可以按返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
阅读更多2024-10-19
大数据实验3： HDFS基础编程
，否则返回文件一行的文本。在 Hadoop 分布式文件系统（HDFS）中的作用是将本地文件系统中的文件 localfile 上传到 HDFS 上的目录 hdfsdir1 中。10、hdfs dfs -
阅读更多2024-10-19
从算盘到云计算：计算机发展的壮丽历程
早期计算器的出现对计算机发展起到了重要作用。从算盘到机械计算器，再到现代计算机的诞生，计算能力不断提升，速度和通用性也得到了显著提升。个人电脑和移动计算机成为生活和工作中不可或缺的工具，云计算使计算机
阅读更多2024-10-19
神经网络构建与训练深度学习模型全过程（PyTorch & TensorFlow）
神经网络（Neural Network）是一种模拟人脑神经元的数学模型，其目的是通过模拟神经元之间的连接与传递信息的方式，来完成复杂的数据处理任务。神经网络由若干层神经元组成，通常分为输入层、隐藏层和
阅读更多2024-10-19

Java 滑动窗口算法详解及通用实现模板案例示范

1. 引言

2. 滑动窗口算法的基本原理

2.1 滑动窗口的应用场景

3. 滑动窗口的通用实现模板

3.1 固定大小的滑动窗口模板

3.2 动态大小的滑动窗口模板

3.3 滑动窗口的时间复杂度分析

4. 案例分析：滑动窗口算法在电商系统中的应用

4.1 案例 1：查找连续订单中的最大销售额

4.2 案例 2：查找满足最低库存要求的最小天数

5. 滑动窗口的时序图

6. 滑动窗口的常见问题

6.1 窗口边界问题

问题描述

示例代码

解决方案

6.2 窗口的初始化问题

问题描述

示例代码

解决方案

6.3 窗口缩小策略问题

问题描述

示例代码

解决方案

相关文章