Indexes of Subarray Sum Problem in Java

为了解决 **Java 中的子数组求和问题**，我们需要找出连续子数组中总和等于特定目标的那些特殊索引。这个问题在算法面试中很常见，尤其是在讨论使用哈希表优化时间复杂度时。

问题陈述

给定一个整数 数组 arr[] 和一个整数 targetSum，确定一个连续子数组的索引，该子数组的和等于 targetSum。如果找到，则返回其开始和结束索引；否则，则指示其不存在。

问题解决方案

我们将使用一个 HashMap 来存储累积和作为键，并以其对应的索引作为值。当我们遍历数组时，我们会维护元素的运行总和。在每次迭代中

1. 如果累积和等于 targetSum，我们确定从索引 0 开始到当前索引结束的子数组可以实现目标和。
2. 如果在 HashMap 中存在当前累积和与 targetSum 的差值，则表示存在一个和为 targetSum 的子数组。此子数组的起始索引紧随 HashMap 中存储的索引之后，而结束索引是当前索引。

让我们在 Java 程序中实现上述方法。

文件名：SubarraySum.java

输出

 
Subarray found from index 1 to index 3   

解释

findSubarrayWithTargetSum() 方法首先初始化一个名为 cumulativeSumMap() 的 HashMap，它将存储遇到的累积和作为键，并将相应的索引作为值。此外，我们还初始化一个 cumulativeSum 变量来跟踪我们在遍历数组时元素的总和。

对于数组中的每个元素，我们将其加到 cumulativeSum 中。如果此累积和等于 targetSum，我们立即知道从开始（索引 0）到当前索引的子数组是解决方案。否则，我们检查 cumulativeSum - targetSum 是否存在于 map 中。如果存在，那么我们就找到了一个具有所需和的子数组，因为存储索引之后的数组部分直到当前索引必须加起来等于 targetSum。

然后我们返回此子数组的索引。如果两个条件都不满足，我们会将当前的累积和和索引存储在 map 中，以便与未来的元素进行比较。如果循环在未找到解决方案的情况下完成，我们返回 {-1, -1} 来表示不存在这样的子数组。main 方法使用示例数组和目标和测试此函数，并在找到解决方案时显示索引。

复杂度分析

时间复杂度

该解决方案的时间复杂度为 O(n)，其中 n 是输入数组的长度。因为

1. 我们在每次迭代中一次遍历数组，更新累积和并遍历 HashMap。
2. HashMap 的插入和检索操作（确定键是否存在）平均为 O(1)，从而确保了我们解决方案的效率。

因此，整个操作需要一次遍历数组，导致线性时间复杂度 O(n)。

空间复杂度

此解决方案的空间复杂度受 HashMap 大小的限制，而 HashMap 的大小与输入数组的长度成正比。所提出解决方案的空间复杂度也为 O(n)，因为我们使用 HashMap 来存储累积和及其对应的索引。

在最坏的情况下，数组中的每个元素都可能具有唯一的累积和，这需要将所有这些和存储在 HashMap 中，从而导致 O(n) 的空间使用。

结论

这种使用累积和和 HashMap 来解决子数组求和问题的方法对于这种特定类型的问题来说是最佳的，因为它具有高效的时间和空间复杂度。关键在于认识到，如果任何时候的累积和减去 targetSum 之前已经被遇到过，那么在之前存储的该累积和的索引和当前索引之间必然存在一个具有所需和的子数组。

这种方法与涉及检查所有可能子数组的朴素（O(n^2)）方法相比有显著改进，使其适用于大型数据集。该算法的线性时间复杂度和简单的实现使其成为高效解决连续子数组求和问题的理想选择。