Java实现：在流式输入中查找连续三整数的最大和（无数组限制）

本文详细介绍了如何在java中，不使用数组的前提下，从连续的整数输入流中找出任意三个连续整数的最大和。文章阐述了滑动窗口的核心思想，通过维护三个变量来模拟窗口滑动，并提供了处理少于三个输入时的特殊逻辑，最终通过示例代码展示了完整的实现过程。

引言

在处理数据流时，我们经常需要对连续的数据子集进行分析。一个常见的场景是，从一系列实时输入的整数中，找出连续三个整数的最大和。本教程将探讨如何在Java中实现这一功能，同时遵守一个特定限制：不允许使用数组。此外，我们还需要处理输入数字不足三个时的特殊情况，即此时应返回所有已输入数字的总和。输入流将以特殊值 999 终止。

核心思想：滑动窗口与变量模拟

由于不能使用数组，我们需要一种机制来“记住”最近的三个数字。这可以通过使用三个独立的整型变量来模拟一个大小为3的“滑动窗口”来实现。当新的数字被输入时，这些变量会进行“轮转”或“移位”，以始终保存最新的三个数字。

假设我们有三个变量：

• num1: 存储窗口中最旧的数字。
• num2: 存储窗口中中间的数字。
• num3: 存储窗口中最新的数字（即当前输入的数字）。

当一个新的数字 newInput 到来时，变量的更新逻辑如下：

立即学习“Java免费学习笔记（深入）”；

Murf AI

AI文本转语音生成工具

下载

1. num1 接收 num2 的值。
2. num2 接收 num3 的值。
3. num3 接收 newInput 的值。

这样，num1, num2, num3 始终代表着最新的三个连续数字。

算法步骤详解

1. 初始化变量：

   • num1, num2, num3: 初始化为 0，用于存储滑动窗口中的三个数字。
   • maxSum: 初始化为 0，用于记录迄今为止发现的最大连续三数之和。
   • inputCount: 初始化为 0，用于统计已输入的有效数字个数。
   • currentInput: 用于存储每次读取的当前数字。

2. 循环读取输入： 使用 Scanner 从控制台持续读取整数，直到遇到终止符 999。

3. 处理每个输入： 对于每个非 999 的输入：

   • inputCount 递增。
   • 执行滑动窗口的移位操作：num1 = num2; num2 = num3; num3 = currentInput;。
   • 判断输入数量：
     • 如果 inputCount < 3（即当前输入的数字不足三个）： 此时，maxSum 应该累加当前所有已输入的数字之和。由于 maxSum 初始化为0，并且在 inputCount < 3 的情况下，它只会累加，因此 maxSum += currentInput; 可以满足需求。例如，如果只输入 7，maxSum 变为 7；如果再输入 2，maxSum 变为 7+2=9。
     • 如果 inputCount >= 3（即已经有三个或更多数字）： 计算当前滑动窗口中三个数字的和：currentWindowSum = num1 + num2 + num3;。 将 currentWindowSum 与 maxSum 进行比较，如果 currentWindowSum 更大，则更新 maxSum = currentWindowSum;。

4. 输出结果： 循环结束后，maxSum 中存储的就是符合条件的最大和。

示例演练

让我们使用示例输入 7 2 9 8 7 6 7 5 9 999 来逐步演示算法的执行过程。

最终结果为 24，与预期相符。

Java 代码实现

import java.util.Scanner;

/**
 * MaxConsecutiveSum类用于在不使用数组的情况下，从流式输入中查找连续三个整数的最大和。
 * 输入以999作为终止符。如果输入的数字少于三个，则返回所有已输入数字的总和。
 */
public class MaxConsecutiveSum {

    public static void main(String[] args) {
        Scanner inputScanner = new Scanner(System.in);
        System.out.print("请输入一系列整数，以999结束: ");

        // num1, num2, num3 构成一个滑动窗口，分别代表窗口中最旧、中间和最新的数字
        int num1 = 0; 
        int num2 = 0; 
        int num3 = 0; 

        // maxSum 存储迄今为止发现的最大连续三数之和。
        // 对于少于三个输入的情况，它也用于累积总和。
        int maxSum = 0; 

        // inputCount 记录有效输入的数字个数
        int inputCount = 0; 
        int currentInput;

        // 循环读取输入，直到遇到终止符999
        while (true) {
            // 尝试读取下一个整数
            try {
                currentInput = inputScanner.nextInt();
            } catch (java.util.InputMismatchException e) {
                System.err.println("无效输入：请输入整数。程序将退出。");
                inputScanner.close();
                return;
            }

            // 如果当前输入是终止符，则退出循环
            if (currentInput == 999) {
                break;
            }

            inputCount++; // 有效输入计数器递增

            // 执行滑动窗口的移位操作
            num1 = num2;
            num2 = num3;
            num3 = currentInput;

            // 根据已输入的数字个数进行不同的处理
            if (inputCount < 3) {
                // 如果输入的数字不足3个，maxSum累加当前输入。
                // 此时num1和num2可能包含0，所以不能直接sum(num1, num2, num3)。
                // 这种方式确保了在少于3个输入时，maxSum就是所有输入的和。
                maxSum += currentInput;
            } else {
                // 当至少有3个数字时，计算当前滑动窗口（num1, num2, num3）的和
                int currentWindowSum = num1 + num2 + num3;
                // 更新maxSum，如果当前窗口的和更大
                if (currentWindowSum > maxSum) {
                    maxSum = currentWindowSum;
                }
            }
        }

        // 输出最终的最大和
        System.out.println("连续三整数的最大和为: " + maxSum);

        // 关闭Scanner，释放资源
        inputScanner.close();
    }
}

注意事项与总结

1. 无数组限制： 这种通过三个独立变量实现滑动窗口的方法，有效规避了使用数组的限制，同时保持了逻辑的清晰性。
2. 边缘情况处理： 算法巧妙地处理了输入数字少于三个的边缘情况。通过在 inputCount < 3 时直接累加 currentInput 到 maxSum，确保了在输入不足时 maxSum 存储的是所有已输入数字的总和。一旦输入达到或超过三个，maxSum 则开始跟踪并更新连续三数的最大和。
3. 输入校验： 示例代码中增加了简单的 try-catch 块来处理非整数输入，提高了程序的健壮性。
4. 时间与空间复杂度：
   • 时间复杂度： 算法只需要遍历一次输入流，对于每个数字执行常数次操作（移位、加法、比较）。因此，时间复杂度为 O(N)，其中 N 是输入的数字总数。
   • 空间复杂度： 算法仅使用了固定数量的几个变量 (`num1