本文旨在探讨如何在java中，不使用数组的情况下，从用户输入流中找出连续三个整数的最大和。文章将详细阐述一种基于滑动窗口和独立变量的算法，并覆盖输入少于三个数时的特殊处理逻辑，最终通过示例代码提供一个完整的解决方案。
在处理数据流时，有时我们需要在不存储整个数据集的前提下，对连续子序列进行操作。本教程将聚焦于一个特定问题：从一系列用户输入的整数中，找出任意连续三个整数的最大和。该过程将持续接收输入，直到遇到终止符999。一个关键的约束是，我们不允许使用数组来存储数据。此外，如果输入的有效数字少于三个，则应计算并输出所有已输入数字的总和。
问题分析与核心思路
核心挑战在于“连续三个整数”和“不使用数组”这两个条件。由于不能使用数组，我们无法方便地存储所有历史数据。然而，“连续”意味着我们只需要关注当前处理的数字及其前两个数字。这引出了“滑动窗口”的概念，但这里的窗口由三个独立的变量而非数组实现。
算法概览：
- 维护滑动窗口： 使用三个独立的整型变量（例如val1, val2, val3）来模拟一个大小为3的滑动窗口，分别存储当前处理数字的前两个数字和当前数字。
- 追踪最大和： 维护一个maxWindowSum变量，用于记录迄今为止遇到的所有三元组中的最大和。
- 处理输入计数： 维护一个inputCount变量，记录已接收的有效（非999）数字数量。这对于判断何时开始计算三元组和以及处理少于三个输入的情况至关重要。
- 处理总和： 维护一个currentTotalSum变量，记录所有有效输入的总和，以应对输入数字不足三个时的要求。
- 终止条件： 当读取到999时，停止输入。
详细算法步骤
-
初始化变量：
立即学习“Java免费学习笔记（深入）”；
- val1 = 0, val2 = 0, val3 = 0：用于存储滑动窗口中的三个数字。初始化为0是安全的，因为在窗口未满3个数字时，它们不会参与到有效的三元组求和中。
- maxWindowSum = 0：存储连续三个数字的最大和。假设输入均为正整数，0是一个合适的初始值。如果可能存在负数，应初始化为Integer.MIN_VALUE。
- inputCount = 0：记录已处理的有效数字数量。
- currentTotalSum = 0：记录所有有效数字的总和。
- 创建Scanner对象以读取用户输入。
-
循环读取输入：
- 在一个while(true)循环中，不断读取下一个整数。
- 如果读取到的数字是999，则跳出循环。
- 否则，说明这是一个有效数字：
- inputCount加1。
- currentTotalSum累加当前数字。
- 执行滑动：val1 = val2，val2 = val3，val3 = 当前读取的数字。
-
判断是否达到3个数字： 如果inputCount大于或等于3：
- 计算当前窗口的和：currentWindowSum = val1 + val2 + val3。
- 更新maxWindowSum：maxWindowSum = Math.max(maxWindowSum, currentWindowSum)。
-
输出最终结果：
- 循环结束后，根据inputCount的值决定输出：
- 如果inputCount < 3（即输入的有效数字不足三个）：输出currentTotalSum。
- 否则（inputCount >= 3）：输出maxWindowSum。
- 循环结束后，根据inputCount的值决定输出：
示例代码
import java.util.Scanner;
public class MaxConsecutiveSumWithoutArrays {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
// 用于存储滑动窗口中的三个数字
int val1 = 0; // 最早的数字
int val2 = 0; // 中间的数字
int val3 = 0; // 最新的数字
// 记录连续三个数字的最大和
int maxWindowSum = 0;
// 记录有效输入数字的数量
int inputCount = 0;
// 记录所有有效输入数字的总和（用于处理少于3个输入的情况）
int currentTotalSum = 0;
System.out.print("请输入数字，以999结束: ");
while (true) {
int num = input.nextInt(); // 读取下一个整数
if (num == 999) {
break; // 遇到999，终止输入
}
inputCount++; // 有效数字计数加1
currentTotalSum += num; // 累加所有有效数字
// 执行滑动窗口更新
val1 = val2;
val2 = val3;
val3 = num; // 将新读取的数字放入窗口最右侧
// 当至少有3个数字时，才开始计算三元组的和
if (inputCount >= 3) {
int currentWindowSum = val1 + val2 + val3;
// 更新最大连续三数和
if (currentWindowSum > maxWindowSum) {
maxWindowSum = currentWindowSum;
}
}
}
// 根据输入数字的数量决定最终输出
if (inputCount < 3) {
System.out.println("输入的有效数字少于3个，总和为: " + currentTotalSum);
} else {
System.out.println("连续三个数字的最大和为: " + maxWindowSum);
}
input.close(); // 关闭Scanner
}
}
注意事项与总结
- 数据类型： 示例代码假设输入数字和它们的和不会超出int类型的范围。如果输入数字可能非常大，应考虑使用long类型。
- 负数处理： 如果输入可能包含负数，maxWindowSum的初始值应设置为Integer.MIN_VALUE，以确保能够正确捕获到负数情况下的最大和。本示例假设输入为正整数，所以0作为初始值是可行的。
- 输入验证： 实际应用中，可能需要对用户输入进行更严格的验证，例如检查是否输入了非整数值。Scanner.nextInt()在遇到非整数输入时会抛出InputMismatchException。
- 效率： 这种基于独立变量的滑动窗口方法具有O(N)的时间复杂度，其中N是输入的数字数量。由于每个数字只处理一次，并且没有额外的存储开销（除了几个固定变量），因此效率非常高。
通过上述方法，我们成功地在不使用数组的限制下，解决了查找连续三个整数最大和的问题，并妥善处理了各种边界情况，如输入数量不足三。这种技巧在内存受限或需要处理无限数据流的场景中非常有用。
