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

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

引言

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

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

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

假设我们有三个变量：

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

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

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

MCP官网

Model Context Protocol（模型上下文协议）

下载

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
     • 如果 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. 输入校验： 示例代码中增加了简单的 try-catch 块来处理非整数输入，提高了程序的健壮性。
4. 时间与空间复杂度：
   • 时间复杂度： 算法只需要遍历一次输入流，对于每个数字执行常数次操作（移位、加法、比较）。因此，时间复杂度为 O(N)，其中 N 是输入的数字总数。
   • 空间复杂度： 算法仅使用了固定数量的几个变量 (`num1