Java中滑动窗口算法和固定窗口算法都属于窗口算法,是比较高效的一种算法,它主要用于处理一些数据包含满足一个特定条件的子串或者子序列问题。
滑动窗口算法的思路是,定义一个窗口,该窗口可以在数据中滑动,通过改变窗口的起始位置和结束位置,来找到满足特定条件的子串或者子序列。以找到一个字符串中所有长度为k的子串中的最大值为例,代码如下:
public static int slideWindow(int[] nums, int k) { int maxSum = Integer.MIN_VALUE; //最大值 int sum = 0; //累加器 int start = 0; //起始位置 for (int i = 0; i< nums.length; i++) { sum += nums[i]; if (i >= k - 1) { maxSum = Math.max(maxSum, sum); sum -= nums[start]; start++; } } return maxSum; }
固定窗口算法的思路是,定义一个固定大小的窗口,对数据进行遍历,并在每一步中更新窗口中的内容,然后对窗口中的内容进行处理。以找到一个数组中长度为k的子数组的平均值为例,代码如下:
public static double fixedWindow(int[] nums, int k) { double sum = 0; //窗口的总和 double res = 0; //答案 for (int i = 0; i< k; i++) { sum += nums[i]; } res = sum / k; for (int i = k; i< nums.length; i++) { sum = sum - nums[i - k] + nums[i]; res = Math.max(res, sum / k); } return res; }
综上所述,滑动窗口和固定窗口算法都是窗口算法的经典应用,能够解决一些需要找到满足特定条件的子串或者子序列的问题,是一种高效的算法。