滑动窗口算法(找出最大连续数，加起来就是一个特定的和)

Question

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。

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

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

Answer 1

我还没有深入研究，但我可以看出你的代码不会按照你的意愿执行。你使用滑动窗口的方式实际上无法找到所有可能的连续数字组合。

您的代码所做的似乎是向前滑动结束索引，直到达到所需的总和，或者到达数组的末尾。然后，使用相同的限制向前滑动起始索引。因此，你最终得到的是一个这样做的窗口：

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

请注意，在任何时候你的窗口都不会是这样的：

[- o - o -]

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