时间戳

首页 > 解决方案 > 滑动窗口算法（查找加起来为特定总和的最大连续数字）

java - 滑动窗口算法（查找加起来为特定总和的最大连续数字）

问题描述

public class Main {
    static final int k = 0;

    public static void main(String[] args) {
        int[] arr = {1, -1, -3, 3, 7, -7, -1, -1, 10, 2};

        int startIndex = 0, endIndex = 0, currentSum = 0;
        int maxDigitsUsed = Integer.MIN_VALUE;


        while(endIndex < arr.length - 1){
            currentSum += arr[endIndex];
            if (currentSum == k && maxDigitsUsed < endIndex - startIndex) {
                maxDigitsUsed = endIndex - startIndex;
            } else {
                endIndex++;
            }
        }


        // moving the startIndex forward when there is a chance to change the sum to k
        while (startIndex <= endIndex) {
            currentSum -= arr[startIndex];
            if (currentSum == k && maxDigitsUsed < endIndex - startIndex) {
                maxDigitsUsed = endIndex - startIndex;

            }
            startIndex++;

        }
 }

我的教授经历了一个简单的滑动窗口算法，该算法检查加起来为指定总和 k 的最大连续数字，在这种情况下 k = 0。

但是，当存在负数时，它似乎不起作用。为什么会这样，我应该如何纠正它？此外，最初的实现应该是一个队列，因此任何基于队列的答案都会非常有帮助！

这个基于数组的实现完全是我的尝试，所以请原谅任何严重的错误。最初的问题只涉及正整数并使用队列而不是数组。

标签： javaqueuesliding-window

解决方案

我对此并没有深入研究，但我可以看出你的代码不会做你想做的事。您执行滑动窗口的方式实际上无法找到所有可能的连续数字组合。

看起来你的代码正在做的是向前滑动结束索引，直到你达到所需的总和，或者到达数组的末尾。然后你用同样的限制向前滑动起始索引。所以你最终得到的是一个执行此操作的窗口：

[o - - - -]
[o o - - -]
[o - o - -]
[o - - o -]
[o - - - o]
[- o - - o]
[- - o - o]
[- - - o o]
[- - - - o]

请注意，您的窗口绝不会像这样：

[- o - o -]

因此，如果这恰好是加起来所需总和的最大窗口，那么您的算法将永远找不到它。所以你需要努力让你的代码点击所有可能的窗口。最明显的方法是使用嵌套循环。您可以将结束索引一直滑动到末尾，然后将起始索引向上加一，重置总和，然后再次将结束索引从新起点滑到末尾。对所有可能的起始索引重复此操作，并且应该覆盖数组上的每个窗口。

推荐阅读