java 滑动窗口-代码示例

滑动窗口是一种常用的算法技巧，用于解决一些数组或字符串相关的问题。它通过维护一个窗口来处理连续的子数组或子字符串，可以实现高效的查找、计算或判断。

下面是一个Java的滑动窗口的示例代码，用于求解一个数组中的最大连续子数组的和。该问题可以通过滑动窗口的方式进行解决。

public int maxSubArray(int[] nums) {
    int maxSum = Integer.MIN_VALUE; // 初始化最大和为最小整数值
    int currentSum = 0; // 当前窗口的和
    // 定义窗口的左右边界
    int left = 0;
    int right = 0;
    // 遍历数组
    while (right < nums.length) {
        // 窗口右边界右移，扩大窗口
        currentSum += nums[right];
        right++;
        // 当窗口的和大于最大和时，更新最大和
        if (currentSum > maxSum) {
            maxSum = currentSum;
        }
        // 当窗口的和小于0时，缩小窗口
        if (currentSum < 0) {
            currentSum = 0;
            left = right;
        }
    }
    return maxSum;
}

在这个示例代码中，我们通过维护一个窗口，不断向右移动来求解最大连续子数组的和。我们初始化最大和为最小整数值，并定义窗口的左右边界为0。然后，我们遍历数组，每次将窗口的右边界右移，并更新当前窗口的和。如果当前窗口的和大于最大和，我们就更新最大和。如果当前窗口的和小于0，说明当前窗口的和对于后续的子数组和没有正向贡献，所以我们将窗口的左边界右移，并将当前窗口的和重置为0。最终，我们返回最大和作为结果。

通过滑动窗口的方式，我们可以在一次遍历中解决这个问题，而不需要使用嵌套循环。这样可以大大提高算法的效率。